NOIP之数论与数论算法

《NOIP之数论与数论算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数论与数论算法一、质数与质因数分解1.质数：也称素数，指除1和它本身以外没有其他因数的正整数。素数有无穷多个。1不是素数。2.质因数分解：任意一个大于1的正整数都可以唯一分解成若干个质数相乘的形式。即：abcdA2*3*5*7.........(Aa为大于的正整数，其中、、、1bcd>=0)3.【例题1】已知正整数N是两个不同质数的乘积，请求出较大的那个质数（洛谷1075）。#includeusingnamespacestd;intmain(){intn=0;inti=2;cin>>n;//找出n的其中一个质因数while(n%i!=0){i++;}intk=n/i

2、;//求出n的另一个质因数//求较大的那个质因数if(kintcnt[10001]={0};//定义数组，保存每个质因数的个数//对给定的整数d进行质因数分解voidseprate(intd){intfactor=2;while(d>=factor){if(d%fact

3、or!=0){factor++;continue;}cnt[factor]++;d=d/factor;}}intmain(){intn=0;scanf("%d",&n);//从2到n依次进行质因数分解//因为n!=2*3*4*....*nfor(inti=2;i<=n;i++){seprate(i);}//输出每个质因数的个数for(inti=2;i<=10000;i++){if(cnt[i]>0){printf("%d%d",i,cnt[i]);}}return0;}提示：因为longlong最大只能存储20的阶乘，所以我们要把N的阶乘，进行拆分，依次求出2、3、4、....、N的

4、质因数。135.【练习】求n!结果有多少个0，2<=n<=10123提示：找1、2、3…..N中，5(5)的倍数、25(5)的倍数、125(5)的倍数……的个数1、2…N中，不大于N且为5的倍数的数，共有N/5个，它们每个可贡献一个5；21、2…N中，不大于N且为25的倍数的数，共有N/5个，它们每个可再次贡献一个5；................................2二、质数筛选（求1到N的所有质数）1.【试除法】：使用2到sqrt(x)试除x，如果x不存在因数则表示x是质数；如果x有因数则表示x不是质数。时间复杂度为：Onn()#include#incl

5、udeintmain(){intn=0,f=0;scanf("%d",&n);for(intx=2;x<=n;x++){f=1;//将标记变量f设为1，默认x是质数for(inti=2;i<=sqrt(x);i++){if(x%i==0){//如果找到x有因数，则表明x不是质数，将标记变量设为0，跳出循环f=0;break;}}if(f==1){printf("%d",x);}}return0;}2.【例题1】求第k小的素数//部分代码已省略intx=2,n=1;//n表示当前已求出的素数是第几个，x表示当前被试除的整数while(n

6、=2;i<=sqrt(x);i++){if(x%i==0){f=0;break;}}if(f==1){n++;}}printf("%d",x);33.【埃氏筛选法】：由质因数分解定理，可以得出,任意合数都可以分解成至少两个质数的乘积，所以质数是不能被再分的。如果x是质数，那么2*x、3*x、4*x、....必然都不是质数。我们可利用此规律筛选出N以内的素数。时间复杂度为:On(loglog)n#include#include#includeintf[10000010]={0};//素数标记数组,若f[i]!=0,则表示i是素数intmain

7、(){intn=0;scanf("%d",&n);memset(&f[0],0x01,sizeof(f));//1、假设n以内的所有整数都是素数f[1]=0;//2、整数1不是素数for(inti=2;i<=sqrt(n);i++){if(f[i]==0){continue;}//3、素数的整数倍必然不是素数for(intj=2*i;j<=n;j+=i){f[j]=0;}}//4、输出所有的素数for(inti=2;i<=n;i++