題目
標題：等差素數列
2,3,5,7,11,13,....是素數序列，
類似：7,37,67,97,127,157 這樣完全由素陣列成的等引數列，叫等差素數數列，
上邊的數列公差為30，長度為6，
2004年，格林與華人陶哲軒合作證明了：存在任意長度的素數等引數列，
這是數論領域一項驚人的成果！
有這一理論為基礎，請你借助手中的計算機，滿懷信心地搜索：
長度為10的等差素數列，其公差最小值是多少？
注意：需要提交的是一個整數，不要填寫任何多余的內容和說明文字，
題解
絮絮叨叨（罵罵咧咧
一開始看到這道題還是有點懵的，畢竟我個數學小白，對素數什么的最發怵了，
然后找了好多大佬的題解都沒看明白，甚至有一個大佬的代碼看的我暈頭轉向~
然后終于被我找到一份能看懂并且覺得非常正確的代碼，思路如下：
思路
兩層回圈，一層回圈用于回圈公差，一層回圈用于回圈起始素數，
需要注意的是，內層回圈起始素數的時候，不能無邊界回圈下去，要設定一個上限，否則外層回圈永遠無法走到下一個公差（自己寫的時候自以為是犯的錯
內層回圈走的時候，只需要判斷：
①這個數是不是素數（作為起始素數最基本的條件）
②判斷從這個素數開始，以cha為公差能否存在連續10個等差的素數，【用ok函式來判斷的】
如果以上兩個條件都滿足，則這就是我們要找的長度為10的等差素數列，其公差的最小值
因為我們是從小到大找的，那我們找到的滿足條件的第一個就是答案~
代碼
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll maxn=1e6+50;
ll a[maxn];
bool ok(ll n,ll cha)
{
for(ll i=0;i<10;i++)
{
if(!a[n+i*cha])return 0;
}
return 1;
}
int main()
{
a[1]=0;
a[2]=1;
a[3]=1;
for(ll i=4;i<=1000000;i++)
{
bool flag=0;
for(ll j=2;j*j<=i;j++)
{
if(i%j==0)
{
flag=1;
break;
}
}
if(flag)a[i]=0;
else a[i]=1;
}
for(ll cha=1;;cha++)
{
for(ll i=2;i<1000000;i++)
{
if(a[i]&&ok(i,cha))
{
printf("%lld\n",cha);
return 0;
}
}
}
}
后記
其實我對素數一直都懷有敬畏之心，希望能找個時間把素數的相關演算法摸摸透，把板子整理齊全~（先給自己挖個坑
要是整理好了，我就把鏈接更新上來！（咕咕咕~
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/3609.html
標籤：C++
上一篇：Qt 的事件監聽和事件過濾