標(biāo)題：等差素數(shù)列

2,3,5,7,11,13,....是素數(shù)序列。
類似：7,37,67,97,127,157 這樣完全由素數(shù)組成的等差數(shù)列，叫等差素數(shù)數(shù)列。
上邊的數(shù)列公差為30，長度為6。

2004年，格林與華人陶哲軒合作證明了：存在任意長度的素數(shù)等差數(shù)列。
這是數(shù)論領(lǐng)域一項驚人的成果！

有這一理論為基礎(chǔ)，請你借助手中的計算機，滿懷信心地搜索：

長度為10的等差素數(shù)列，其公差最小值是多少？

注意：需要提交的是一個整數(shù)，不要填寫任何多余的內(nèi)容和說明文字。

分析：這道題目思路挺簡單的，就是用線性篩選法把10^6內(nèi)的素數(shù)篩選出來，然后從大到小枚舉然后去驗證

關(guān)鍵是一定要掌握線性篩選法。。。

1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 #define ll long long 5 const int maxn=1e6; 6 int check[maxn]={0}; 7 int prime[maxn]; 8 int pos; 9 10 void init(){//線性篩選法 11 for( ll i=2; i<maxn; i++ ){ 12 if(!check[i]){ 13 prime[pos++]=i; 14 } 15 for( ll j=0; j<pos&&i*prime[j]<maxn; j++ ){ 16 check[i*prime[j]]=1; 17 if(i%prime[j]==0) break; 18 } 19 } 20 } 21 22 int main(){ 23 init(); 24 for(int k=1; k*10<maxn; k++ ){//k為公差 25 for( int i=0; i<pos; i++ ){ 26 int flag=1,temp=prime[i]; 27 for( int j=1; j<10; j++ ){ 28 if(temp+k>=maxn||check[temp+k]==1){ 29 flag=0; 30 break; 31 } 32 else{ 33 temp+=k; 34 } 35 } 36 if(flag==1){ 37 cout<<k<<" "<<prime[i]<<endl; 38 } 39 } 40 } 41 42 return 0; 43 } 44 //210 199

?

轉(zhuǎn)載于:https://www.cnblogs.com/Bravewtz/p/10344482.html

總結(jié)

以上是生活随笔為你收集整理的第八届蓝桥杯省赛第二题---等差素数列的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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