素?cái)?shù)篩選法的思想：對(duì)于不超過N的每個(gè)正整數(shù)，刪除2P,3P,4P……，當(dāng)處理完所有數(shù)之后，還沒有被刪除的就是素?cái)?shù)。

按照上述思想寫成的簡(jiǎn)單篩選法代碼如下：

memset(vis,o,sizeof(vis)); for(int i=2;i<N;i++) for(int j=i*2;j<=N;j+=i) vis[j]=1; //用vis數(shù)組存儲(chǔ)數(shù)j是否被刪除的信息。

下面我們想想如何改進(jìn)：

1.由唯一分解定理：每個(gè)正整數(shù)可以寫成n=a1^p1*a2^p2……（其中a1,a2是質(zhì)數(shù)）

改進(jìn)代碼：

memset(vis,0,sizeof(vis)); for(int i=2;i*i<=m;i++) if(!vis[i])//判斷i是質(zhì)數(shù)， for(int j=i*i;j<=n;j+=i) vis[j]=1;//直接從i*i開始

這個(gè)改進(jìn)了的代碼也會(huì)有重復(fù)篩選的情況存在，比如數(shù)16，81等

下面給出最優(yōu)的歐拉篩法，真正的o(n)復(fù)雜度

const int N=1000000+5; int check[N],prime[N]; memset(prime,0,sizeof(prime)); memset(check,0,sizeof(check)); int ptot=0; for(int i=2;i<=n;i++){ if(!check[i]) prime[ptot++]=i; for(int j=0;j<ptot;j++){ if(prime[j]*i>n) break; check[prime[j]*i)=1; if(i%prime[j]==0) break;//區(qū)別第二個(gè)代碼的一步 } }


歐拉篩法和第二個(gè)代碼 思想類似，只是多了關(guān)鍵了一步，“ifi%prime[j]==0) break;"

為什么要這樣做呢？

分析第二個(gè)代碼，它極大地避免了重復(fù)的篩選，它的外層篩選只選取質(zhì)數(shù)，內(nèi)層循環(huán)避免了2*3和3*2的這種重復(fù)篩選

但是像24這種既可以分解為2*12，又可以分解為3*8的來(lái)說，第二個(gè)代碼就沒有避免對(duì)24的重復(fù)篩選。

下面給出歐拉篩法里面關(guān)鍵一步的原理證明

設(shè)合數(shù)n的最小質(zhì)因數(shù)為p，另一個(gè)比它大的質(zhì)因數(shù)為p1，設(shè)n=p*m=p1*m1;因?yàn)閜和p1互質(zhì)，則p|m1;另外可以知道m(xù)1<m，故若在i為m1的時(shí)候?qū)篩選一次的話，那么在后面i為m的時(shí)候，又會(huì)對(duì)n篩選一次，所以需要判斷m1%p==0；（可以證明起沖要性）這樣就會(huì)只在i為m的時(shí)候?qū)進(jìn)行篩選，實(shí)現(xiàn)了對(duì)每一個(gè)數(shù)只篩選一次。

總結(jié)

以上是生活随笔為你收集整理的素数筛选以及优化分析的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。