NOIP之數(shù)論與數(shù)論算法

《NOIP之數(shù)論與數(shù)論算法》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、數(shù)論與數(shù)論算法一、質(zhì)數(shù)與質(zhì)因數(shù)分解1.質(zhì)數(shù)：也稱素數(shù)，指除1和它本身以外沒有其他因數(shù)的正整數(shù)。素數(shù)有無窮多個。1不是素數(shù)。2.質(zhì)因數(shù)分解：任意一個大于1的正整數(shù)都可以唯一分解成若干個質(zhì)數(shù)相乘的形式。即：abcdA?2*3*5*7.........(Aa為大于的正整數(shù)，其中、、、1bcd>=0)3.【例題1】已知正整數(shù)N是兩個不同質(zhì)數(shù)的乘積，請求出較大的那個質(zhì)數(shù)（洛谷1075）。#includeusingnamespacestd;intmain(){intn=0;inti=2;cin>>n;//找出n的其中一個質(zhì)因數(shù)while(n%i!=0){i++;}intk=n/i

2、;//求出n的另一個質(zhì)因數(shù)//求較大的那個質(zhì)因數(shù)if(kintcnt[10001]={0};//定義數(shù)組，保存每個質(zhì)因數(shù)的個數(shù)//對給定的整數(shù)d進行質(zhì)因數(shù)分解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依次進行質(zhì)因數(shù)分解//因為n!=2*3*4*....*nfor(inti=2;i<=n;i++){seprate(i);}//輸出每個質(zhì)因數(shù)的個數(shù)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、質(zhì)因數(shù)。135.【練習】求n!結(jié)果有多少個0，2<=n<=10123提示：找1、2、3…..N中，5(5)的倍數(shù)、25(5)的倍數(shù)、125(5)的倍數(shù)……的個數(shù)1、2…N中，不大于N且為5的倍數(shù)的數(shù)，共有N/5個，它們每個可貢獻一個5；21、2…N中，不大于N且為25的倍數(shù)的數(shù)，共有N/5個，它們每個可再次貢獻一個5；................................2二、質(zhì)數(shù)篩選（求1到N的所有質(zhì)數(shù)）1.【試除法】：使用2到sqrt(x)試除x，如果x不存在因數(shù)則表示x是質(zhì)數(shù)；如果x有因數(shù)則表示x不是質(zhì)數(shù)。時間復雜度為：Onn()#include#incl

5、udeintmain(){intn=0,f=0;scanf("%d",&n);for(intx=2;x<=n;x++){f=1;//將標記變量f設(shè)為1，默認x是質(zhì)數(shù)for(inti=2;i<=sqrt(x);i++){if(x%i==0){//如果找到x有因數(shù)，則表明x不是質(zhì)數(shù)，將標記變量設(shè)為0，跳出循環(huán)f=0;break;}}if(f==1){printf("%d",x);}}return0;}2.【例題1】求第k小的素數(shù)//部分代碼已省略intx=2,n=1;//n表示當前已求出的素數(shù)是第幾個，x表示當前被試除的整數(shù)while(n

6、=2;i<=sqrt(x);i++){if(x%i==0){f=0;break;}}if(f==1){n++;}}printf("%d",x);33.【埃氏篩選法】：由質(zhì)因數(shù)分解定理，可以得出,任意合數(shù)都可以分解成至少兩個質(zhì)數(shù)的乘積，所以質(zhì)數(shù)是不能被再分的。如果x是質(zhì)數(shù)，那么2*x、3*x、4*x、....必然都不是質(zhì)數(shù)。我們可利用此規(guī)律篩選出N以內(nèi)的素數(shù)。時間復雜度為:On(loglog)n#include#include#includeintf[10000010]={0};//素數(shù)標記數(shù)組,若f[i]!=0,則表示i是素數(shù)intmain

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