素?cái)?shù)篩法
素?cái)?shù)是ACM中數(shù)論題目常常涉及到得問題。最基本的問題就是如何判斷一個數(shù)是素?cái)?shù)以及如何快速的打出題目涉及范圍的素?cái)?shù)表。當(dāng)然數(shù)論中關(guān)于素?cái)?shù)的問題會比較復(fù)雜，在這里僅就素?cái)?shù)的不同篩法做出總結(jié)。
素?cái)?shù)，就是只有1和自身兩個約數(shù)的正整數(shù)。2是最小的素?cái)?shù)。根據(jù)定義，我們就可以直接判斷一個數(shù)字n是否是素?cái)?shù)。優(yōu)化后的復(fù)雜度是O(n*sqrt(n))。至于為什么，我就不做贅述了，自己可以稍作思考。但是，在大規(guī)模的數(shù)據(jù)范圍時，這個算法會耗時太多，顯得十分低效！不信可以輸入n=1000000試試哈~~~~
下面介紹第二種較為高效的算法-----篩法。
具體篩法是：先把n個自然數(shù)按次序排列起來。1不是質(zhì)數(shù)，也不是合數(shù)，要劃去。第二個數(shù)2是質(zhì)數(shù)留下來，而把2后面所有能被2整除的數(shù)都劃去。2后面第一個沒劃去的數(shù)是3，把3留下，再把3后面所有能被3整除的數(shù)都劃去。3后面第一個沒劃去的數(shù)是5，把5留下，再把5后面所有能被5整除的數(shù)都劃去。這樣一直做下去，就會把不超過N的全部合數(shù)都篩掉，留下的就是不超過N的全部質(zhì)數(shù)。因?yàn)橄ＥD人是把數(shù)寫在涂臘的板上，每要劃去一個數(shù)，就在上面記以小點(diǎn)，尋求質(zhì)數(shù)的工作完畢后，這許多小點(diǎn)就像一個篩子，所以就把埃拉托斯特尼的方法叫做“埃拉托斯特尼篩法”，簡稱“篩法”。
當(dāng)然你可以手動操作一下1~30內(nèi)的篩選過程。
[c-sharp] view plain copy// 1：這是最原始的篩法，還有待優(yōu)化 #define Max 1000000 bool PRime[Max]; void IsPrime(){ prime[0]=prime[1]=0;prime[2]=1; for(int i=3;i<max;i++) prime[i]=i%2==0?0:1; int t=(int)sqrt(Max*1.0); for(int i=3;i<=t;i++) if(prime[i]) for(int j=i;j<Max;j+=i) prime[j]=0; } //2：優(yōu)化后的篩法，手動地模擬原始篩法就可以發(fā)現(xiàn)，某個數(shù)字可能被不止一次地刪去 // 優(yōu)化后的篩法就可以避免這種不必要的刪去操作 #define Max 1000000 bool prime[Max]; void IsPrime(){ prime[0]=prime[1]=0;prime[2]=1; for(int i=3;i<max;i++) prime[i]=i%2==0?0:1; int t=(int)sqrt(Max*1.0); for(int i=3;i<=t;i++) if(prime[i]) for(int j=i*i;j<Max;j+=2*i)//優(yōu)化 prime[j]=0; }
是不是上述優(yōu)化后的篩法就是最優(yōu)的呢？記得去年暑期培訓(xùn)的時候博士還給我們介紹了獨(dú)創(chuàng)的優(yōu)化，這樣在數(shù)據(jù)規(guī)模較大的時候，優(yōu)化效果顯得更明顯，可是上級一試哦~~~
[c-sharp] view plain copy//這就是素?cái)?shù)的二次篩法，博士獨(dú)創(chuàng)~~~~~ //與前兩種篩法不同，此種篩法中prime[i]=2*i+3（即：我們只存儲奇數(shù)，偶數(shù)肯定不是素?cái)?shù)的） #define Max 1000000 bool prime[Max>>1]; void IsPrime(){ memset(prime,true,sizeof(prime)); int n=Max>>1,m=(int)(sqrt(Max*1.0)/2.0); for(int i=0;i<=m;i++) if(prime[i]) for(int j=2*i*i+6*i+3;j<=n;j+=2*i+3) isprime[j]=false; }
博文來源：http://blog.csdn.net/once_hnu/article/details/6302283
新聞熱點(diǎn)
疑難解答
