C++如何实现求等差素数列-创新互联
小编这次要给大家分享的是C++如何实现求等差素数列,文章内容丰富,感兴趣的小伙伴可以来了解一下,希望大家阅读完这篇文章之后能够有所收获。
成都创新互联是一家网站设计公司,集创意、互联网应用、软件技术为一体的创意网站建设服务商,主营产品:成都响应式网站建设公司、品牌网站制作、成都营销网站建设。我们专注企业品牌在网站中的整体树立,网络互动的体验,以及在手机等移动端的优质呈现。成都网站设计、成都网站建设、外贸网站建设、移动互联产品、网络运营、VI设计、云产品.运维为核心业务。为用户提供一站式解决方案,我们深知市场的竞争激烈,认真对待每位客户,为客户提供赏析悦目的作品,网站的价值服务。题目
标题:等差素数列
2,3,5,7,11,13,....是素数序列。
类似:7,37,67,97,127,157 这样完全由素数组成的等差数列,叫等差素数数列。
上边的数列公差为30,长度为6。
2004年,格林与华人陶哲轩合作证明了:存在任意长度的素数等差数列。
这是数论领域一项惊人的成果!
有这一理论为基础,请你借助手中的计算机,满怀信心地搜索:
长度为10的等差素数列,其公差最小值是多少?
注意:需要提交的是一个整数,不要填写任何多余的内容和说明文字。
题解
絮絮叨叨(骂骂咧咧
一开始看到这道题还是有点懵的,毕竟我个数学小白,对素数什么的最发怵了。
然后找了好多大佬的题解都没看明白,甚至有一个大佬的代码看的我晕头转向~
然后终于被我找到一份能看懂并且觉得非常正确的代码,思路如下:
思路
两层循环,一层循环用于循环公差,一层循环用于循环起始素数。
需要注意的是,内层循环起始素数的时候,不能无边界循环下去,要设置一个上限,否则外层循环永远无法走到下一个公差(自己写的时候自以为是犯的错
内层循环走的时候,只需要判断:
①这个数是不是素数(作为起始素数最基本的条件)
②判断从这个素数开始,以cha为公差能否存在连续10个等差的素数。【用ok函数来判断的】
如果以上两个条件都满足,则这就是我们要找的长度为10的等差素数列,其公差的最小值
因为我们是从小到大找的,那我们找到的满足条件的第一个就是答案~
#include#include #include #include 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; } } } }
分享标题:C++如何实现求等差素数列-创新互联
链接分享:http://pwwzsj.com/article/dpdjep.html