目录
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 ;
}