基础知识1

目录

1、gcd最大公因数

2、最小公倍数

3、素数问题

①简单数学求法

②素数筛

③线性筛

---

1、gcd最大公因数

 int gcd(int a,int b){return b==0?a:gcd(b,a%b);}

做题过程中，如果数据太大，需要边做边对分子分母进行约分

2、最小公倍数

 int a,b;scanf("%d %d",&a,&b);int t=a*b/gcd(a,b);   //t为a和b的最小公倍数 printf("%d\n",t);

3、素数问题

①简单数学求法

int isprime(int a){if(a<=1) return 0;if(a==2) return 1;int temp=sqrt(a);   //记得加数学头文件for(int i=2;i<=temp;i++){if(a%i!=0) continue;else return 0;}return 1;}

当题目限制代码运行时间时，就要用素数筛或者欧拉筛

②素数筛

素数筛思想：初始化数组全为0，循环从2开始，把素数的倍数标记为合数，没被标记的就是素数

缺点：存在重复标记，比如6会先被2标记一遍，再被3标记一遍

 #include<stdio.h>#define MAX_N 100​int prime[MAX_N+5]={0};//全部初始化为0void is_prime(){for(int i=2;i<=MAX_N;i++){if(prime[i]) continue; //合数标记为1for(int j=2;j*i<=MAX_N;j++){prime[i*j]=1;//标记素数的倍数为合数}}return;}int main(){is_prime();for(int i=2;i<=MAX_N;i++){if(prime[i]) continue;printf("%d\n",i);}return 0;}

③线性筛

线性筛：比素数筛高效，优化素数筛的重复标记问题

素数筛：一个合数可能被多次标记

线性筛：时间复杂度：O（n) 空间复杂度：O（n)

算法：利用M标记整数N，其中M是除N外最大的因子，N=M*p;

eg:若N=30，则算法中的M、p分别为15,2

若M=25，则算法中的N都有哪些？ 50,75,125

找到规律：M%p==0，则M*p=N(最大)

 int prime[MAX_N+1]={0};void is_prime(){for(int i=2;i<=MAX_N;i++){if(!prime[i]) prime[++prime[0]]=i;for(int j=1;j<=prime[0];j++){if(prime[j]*i>MAX_N) break;prime[prime[j]*i]=1;if(i%prime[j]==0) break;}}return ;}