素數篩法
素數是ACM中數論題目常常涉及到得問題。最基本的問題就是如何判斷一個數是素數以及如何快速的打出題目涉及范圍的素數表。當然數論中關于素數的問題會比較復雜，在這里僅就素數的不同篩法做出總結。
素數，就是只有1和自身兩個約數的正整數。2是最小的素數。根據定義，我們就可以直接判斷一個數字n是否是素數。優(yōu)化后的復雜度是O(n*sqrt(n))。至于為什么，我就不做贅述了，自己可以稍作思考。但是，在大規(guī)模的數據范圍時，這個算法會耗時太多，顯得十分低效！不信可以輸入n=1000000試試哈~~~~
下面介紹第二種較為高效的算法-----篩法。
具體篩法是：先把n個自然數按次序排列起來。1不是質數，也不是合數，要劃去。第二個數2是質數留下來，而把2后面所有能被2整除的數都劃去。2后面第一個沒劃去的數是3，把3留下，再把3后面所有能被3整除的數都劃去。3后面第一個沒劃去的數是5，把5留下，再把5后面所有能被5整除的數都劃去。這樣一直做下去，就會把不超過N的全部合數都篩掉，留下的就是不超過N的全部質數。因為希臘人是把數寫在涂臘的板上，每要劃去一個數，就在上面記以小點，尋求質數的工作完畢后，這許多小點就像一個篩子，所以就把埃拉托斯特尼的方法叫做“埃拉托斯特尼篩法”，簡稱“篩法”。
當然你可以手動操作一下1~30內的篩選過程。
[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ā)現，某個數字可能被不止一次地刪去 // 優(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)的呢？記得去年暑期培訓的時候博士還給我們介紹了獨創(chuàng)的優(yōu)化，這樣在數據規(guī)模較大的時候，優(yōu)化效果顯得更明顯，可是上級一試哦~~~
[c-sharp] view plain copy//這就是素數的二次篩法，博士獨創(chuàng)~~~~~ //與前兩種篩法不同，此種篩法中prime[i]=2*i+3（即：我們只存儲奇數，偶數肯定不是素數的） #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
新聞熱點
疑難解答
