淺談C++如何求等差素數(shù)列

更新時間：2020年07月27日 17:28:34 作者：AnranWu

這篇文章主要介紹了淺談C++如何求等差素數(shù)列，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

題目

標(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)容和說明文字。

題解

絮絮叨叨（~~罵罵咧咧~~

一開始看到這道題還是有點懵的，畢竟我個數(shù)學(xué)小白，對素數(shù)什么的最發(fā)怵了。

然后找了好多大佬的題解都沒看明白，甚至有一個大佬的代碼看的我暈頭轉(zhuǎn)向~

然后終于被我找到一份能看懂并且覺得非常正確的代碼，思路如下：

思路

兩層循環(huán)，一層循環(huán)用于循環(huán)公差，一層循環(huán)用于循環(huán)起始素數(shù)。

需要注意的是，內(nèi)層循環(huán)起始素數(shù)的時候，不能無邊界循環(huán)下去，要設(shè)置一個上限，否則外層循環(huán)永遠(yuǎn)無法走到下一個公差（自己寫的時候自以為是犯的錯

內(nèi)層循環(huán)走的時候，只需要判斷：
①這個數(shù)是不是素數(shù)（作為起始素數(shù)最基本的條件）
②判斷從這個素數(shù)開始，以cha為公差能否存在連續(xù)10個等差的素數(shù)?！居胦k函數(shù)來判斷的】

如果以上兩個條件都滿足，則這就是我們要找的長度為10的等差素數(shù)列，其公差的最小值

因為我們是從小到大找的，那我們找到的滿足條件的第一個就是答案~

#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;
			}
		}
	}
}

后記

其實我對素數(shù)一直都懷有敬畏之心，希望能找個時間把素數(shù)的相關(guān)算法摸摸透，把板子整理齊全~（先給自己挖個坑

要是整理好了，我就把鏈接更新上來！（咕咕咕~

到此這篇關(guān)于淺談C++如何求等差素數(shù)列的文章就介紹到這了,更多相關(guān)C++ 等差素數(shù)列內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: