目录

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};//全部初始化为0
 void is_prime(){
     for(int i=2;i<=MAX_N;i++){
         if(prime[i]) continue; //合数标记为1
         for(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 ;
 }