篩選法求素?cái)?shù)要比普通的求素?cái)?shù)方法更加快速，雖然在一些小范圍內(nèi)看不出多大差別，但是當(dāng)范圍大到一定程度，普通求素?cái)?shù)的方法就會(huì)顯得比較耗時(shí)，在做一些編程題的時(shí)候特別容易超時(shí)
我們就拿1000以?xún)?nèi)的素?cái)?shù)來(lái)說(shuō)

普通的方法（可能和我的不一樣，但是都是按照定義來(lái)的，意思差不多） #include<iostream> using namespace std; int main() {int a[200];int i,j,cnt=0;for(i=2;i<1000;i++){for(j=2;j<=i;j++){if(i%j==0)break;}if(i==j)a[cnt++]=i;這樣就可以把1000以?xún)?nèi)的素?cái)?shù)全部存到數(shù)組a中elsecontinue;}for(int i=0;i<=cnt;i++)cout<<a[i]<<endl; }

可以看到1000以?xún)?nèi)的每一個(gè)數(shù)都要進(jìn)行一次第二個(gè)for循，而且第二個(gè)for循環(huán)每一次都要循環(huán)完，這樣就耗時(shí)

接下來(lái)用篩選法求素?cái)?shù)來(lái)試試 #include<iostream> using namespace std; int main() {int a[1000]={0};//這里最好初始化一下，因?yàn)橛袝r(shí)候取數(shù)組大了數(shù)組里邊的初始值不是0而是一些后臺(tái)的垃圾數(shù)據(jù)int b[1000]={0};int cnt=0;for(int i=2;i<1000;i++){if(a[i]==0){b[cnt++]=i;for(int j=2;i*j<1000;j++)a[j*i]=1;//所有是素?cái)?shù)的倍數(shù)的數(shù)都可以去除}}for(int i=0;i<cnt;i++)cout<<b[i]<<endl;}

可以看出來(lái)代碼明顯要短，可能代碼比普通代碼要難理解一點(diǎn)
至于為啥它不用再?gòu)?~n每一個(gè)都除一遍，因?yàn)槊恳粋€(gè)不是素?cái)?shù)的數(shù)都是由一些比自己小的兩個(gè)整數(shù)相乘得到
篩選法求素?cái)?shù)又是從2（本身是素?cái)?shù)）開(kāi)始，之后的像4，6，8，都會(huì)因?yàn)槭?的倍數(shù)而使a[4],a[6],a[8]的值從0變成1；
不用進(jìn)行判斷，以此類(lèi)推那些比自己小的數(shù)只要不是素?cái)?shù)都已經(jīng)使數(shù)組對(duì)應(yīng)值變成1，由此把所有素?cái)?shù)找出來(lái)，比普通的要簡(jiǎn)單多

總結(jié)

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

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