蚌埠的网站建设,wordpress菜单调用,品牌标志logo大全,个人备案网站做购物网站可以不目录 1、gcd最大公因数
2、最小公倍数
3、素数问题
①简单数学求法
②素数筛
③线性筛 1、gcd最大公因数 int gcd(int a,int b){return b0?a:gcd(b,a%b);}
做题过程中#xff0c;如果数据太大#xff0c;需要边做边对分子分母进行约分
2、最小公倍数 int a,b;scanf(0?a:gcd(b,a%b);}
做题过程中如果数据太大需要边做边对分子分母进行约分
2、最小公倍数 int a,b;scanf(%d %d,a,b);int ta*b/gcd(a,b); //t为a和b的最小公倍数 printf(%d\n,t);
3、素数问题
①简单数学求法
int isprime(int a){if(a1) return 0;if(a2) return 1;int tempsqrt(a); //记得加数学头文件for(int i2;itemp;i){if(a%i!0) continue;else return 0;}return 1;}
当题目限制代码运行时间时就要用素数筛或者欧拉筛
②素数筛
素数筛思想初始化数组全为0循环从2开始把素数的倍数标记为合数没被标记的就是素数
缺点存在重复标记比如6会先被2标记一遍再被3标记一遍 #includestdio.h#define MAX_N 100int prime[MAX_N5]{0};//全部初始化为0void is_prime(){for(int i2;iMAX_N;i){if(prime[i]) continue; //合数标记为1for(int j2;j*iMAX_N;j){prime[i*j]1;//标记素数的倍数为合数}}return;}int main(){is_prime();for(int i2;iMAX_N;i){if(prime[i]) continue;printf(%d\n,i);}return 0;} ③线性筛
线性筛比素数筛高效优化素数筛的重复标记问题
素数筛一个合数可能被多次标记
线性筛时间复杂度On) 空间复杂度On)
算法利用M标记整数N其中M是除N外最大的因子NM*p;
eg:若N30则算法中的M、p分别为15,2
若M25则算法中的N都有哪些 50,75,125
找到规律M%p0则M*pN(最大) int prime[MAX_N1]{0};void is_prime(){for(int i2;iMAX_N;i){if(!prime[i]) prime[prime[0]]i;for(int j1;jprime[0];j){if(prime[j]*iMAX_N) break;prime[prime[j]*i]1;if(i%prime[j]0) break;}}return ;}
