一、问题描述
2,3,5,7,11,13,.... 是素数序列。 类似:7,37,67,97,127,157这样完全由素数组成的等差数列,叫等差素数数列。
上边的数列公差为 30,长度为 6。
2004 年,格林与华人陶哲轩合作证明了:存在任意长度的素数等差数列。 这是数论领域一项惊人的成果!
有这一理论为基础,请你借助手中的计算机,满怀信心地搜索:
长度为 10 的等差素数列,其公差最小值是多少?
二、题目要求
考察
素数判断建议用时10~20min
三、问题分析
首先,对于素数的判断,只能被1和自身整除的数为素数。单独构造一个函数,把6000以内的素数存储到数组中。
判断函数主要判断数字是否为素数,主函数使用三重for循环,第一层是数组内存储的所有素数,第二层是等差数列的公差,第三层是10个符合条件的素数。
如果a[i]+j*k还是素数,判断10次之后,任然成立,则输出当前位置的公差j,当前的公差就是所求的结果。
四、编码实现
//头文件包含sqrt开根号 usingnamespacestd; booljudge(intn)//判断是不是素数 { inti; for(i=2;i<=sqrt(n);i++)//使用开根号减少数据量 { if(n%i==0) returnfalse;//返回错误 } returntrue;//返回正确} intmain() { inti,j,k,length=0,a[5000],sum=0;//定义数组的长度 for(i=2;i<6000;i++)//循环6000以内的所有素数 { if(judge(i))//是素数 { a[length++]=i;//存储到数组 } } for(i=0;i<length;i++)//第一层循环 { for(j=1;j<500;j++)//第二层循环 { sum=0;//初始值 for(k=0;k<10;k++)//第三层for循环 { if(judge(a[i]+j*k))//判断接下来10个数字 { sum++;//符合条件 } } if(sum==10)//成功找到 { cout<<j;//输出公差 exit(0);//退出循环 } } } return0; }
五、输出结果
结果具体为:210