2018-2-28

首先我們得明確一個概念，那就是什么是素數，據我的了解，素數就是除了1和它本身之外，不存在其他的因數的數。

1.素性測試

判斷給定的數n是否是素數

這應該是最簡單的了，直接從2至n，如果存在n對其求余為0的話，那就不是素數了，這里可以降低我們的復雜度，想一下，如果一個數i是n的因子，那么n/i也必定是n的因子，不妨設i<=n/i，那么i最大的值就是sqrt(n)了，那么我們的循環也只要從2到sqrt(n)就可以了，因為這個算法比較普遍，我就不附上代碼了。

2.埃氏篩法

求出給定整數n以內有多少個素數

如果用上面的算法，那么n以內的所有數都要進行一遍素數測試，那么時間復雜度為O(n^2)，可想而知這樣的效果不是特別好。
對于2而言，2的倍數4,6,8…那就都不是素數了，
對于3而言，3的倍數6,9,12…那也都不是素數了，
如果當前的數m是素數，那么m的倍數就都不是倍數了，有的人可能會問，為什么m就是素數呢，我們想一下如果m不是素數的話，那么它一定可以表示為p*q的積，不妨我們設這里的p為素數（如果p不是素數還可以再拆，直至變為素數），那么我們在遇到p這個素數的時候，就已經把m，這個素數p的倍數劃掉了，所以這樣反復操作就能得到我們要的素數了。

#include<iostream> #include<cstring> using namespace std;const int N = 100; bool is_prime[N+1]; int prime[N+1];int main(){memset(is_prime,true,sizeof(is_prime));is_prime[0]=false;is_prime[1]=false;int cnt=0;for (int i=2;i<=N;i++){if (is_prime[i]){prime[cnt++]=i;for (int j=i*i;j<=N;j+=i){is_prime[j]=false;}}}for (int i=0;i<cnt;i++){cout<<prime[i]<<" ";}cout<<"cnt="<<cnt<<endl;// for (int i=2;i*i<=N;i++){// if (is_prime[i]){// for (int j=i*i;j<=N;j+=i){// is_prime[j]=false;// }// }// }// int cnt=0;// for (int i=0;i<=N;i++){// if (is_prime[i]) prime[cnt++]=i;// }// for (int i=0;i<cnt;i++){// cout<<prime[i]<<" ";// }// cout<<"cnt="<<cnt<<endl;return 0; }

這里的j有的人可能會想從2*i開始，其實從2*i到(i-1)*i都已經在’i’為2到i-1的時候被計算過了，所以我們這里會選擇從i*i開始。

3.區間篩法

給定區間[a,b)，求出他們兩個數之間素數的個數

對于[a,b)內的合數而言，它們的因子應該在2到sqrt(b)之間，那么我們只要把2到sqrt(n)的倍數在給定區間[a,b)的數篩掉就可以了，為了節省我們的存儲空間，我們可以將[a,b)，左移到[0,b-a)就可以了。

#include<iostream> #include<cstring> using namespace std;typedef long long int ll; const int N = 1000000; bool is_prime_small[N+1],is_prime[N+1]; ll a,b;int main(){while (cin>>a>>b){memset(is_prime,true,sizeof(is_prime));memset(is_prime_small,true,sizeof(is_prime_small));is_prime_small[0]=false;is_prime_small[1]=false;if (a==0){is_prime[0]=false;is_prime[1]=false;}else if (a==1){is_prime[0]=false;}for (ll i=2;i*i<b;i++){if (is_prime_small[i]){for (ll j=i*i;j<b;j+=i){if (j>=a) is_prime[j-a]=false;//在對應區間的數就不是素數了}for (ll j=i*i;j*j<b;j+=i) is_prime_small[j]=false;//將[2,sqrt(b))內的素數篩出來}}int cnt=0;for (ll i=0;i<b-a;i++){if (is_prime[i]){cnt++;cout<<i+a<<" ";}}cout<<"cnt="<<cnt<<endl;}return 0; }

除此之外還有其他素數有關的算法，不過程序設計競賽主要就是涉及這三種。

最后給一個第八屆藍橋杯b組的試題：

2,3,5,7,11,13,....是素數序列。 類似：7,37,67,97,127,157 這樣完全由素數組成的等差數列，叫等差素數數列。 上邊的數列公差為30，長度為6。2004年，格林與華人陶哲軒合作證明了：存在任意長度的素數等差數列。 這是數論領域一項驚人的成果！有這一理論為基礎，請你借助手中的計算機，滿懷信心地搜索：長度為10的等差素數列，其公差最小值是多少？注意：需要提交的是一個整數，不要填寫任何多余的內容和說明文字。

如果我沒記錯的話，當時比賽的時候好像是錯的。。。
首先我們需要把1000000以內的所有素數篩選出來，這樣可以簡化我們后邊的計算，然后我們對d以及首項a1進行遍歷，然后依次判斷即可。
剛開始的時候我還在糾結一個問題，也就是說如果當前的cnt正好等于M=10，那么是否存在a1-d正好也是素數，那么這里是不是就多了一個了，變成M+1個了，后來我發現，不存在的，在我這里，以a1-d為首項的等差數列的d’一定小于d。

#include<iostream> #include<cstring> using namespace std;const int N = 1000000, M = 10; bool is_prime[N+1];int main(){memset(is_prime,true,sizeof(is_prime));for (int i=2;i*i<=N;i++){if (is_prime[i]){for (int j=i*i;j<=N;j+=i){is_prime[j]=false;}}}int i,cnt;bool flag=false;for (i=2;;i++){for (int j=2;j<=N;j++){if (!is_prime[j]) continue;cnt=1;for (int k=j+i;k<=N;k+=i){if (!is_prime[k]||cnt>M) break;if (is_prime[k]){cnt++;}}if (cnt==M){flag=true;break;}}if (flag) break;}cout<<i<<endl;return 0; }

雖然運行的時候停頓了一下，但是最后還是得到了結果210。

總結

以上是生活随笔為你收集整理的判断素数或者求出素数的基本算法 《挑战程序设计竞赛》的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。