题目如下:
2,3,5,7,11,13,…是素数序列。
类似:7,37,67,97,127,157 这样完全由素数组成的等差数列,叫等差素数数列。
上边的数列公差为30,长度为6。
2004年,格林与华人陶哲轩合作证明了:存在任意长度的素数等差数列。
这是数论领域一项惊人的成果!
有这一理论为基础,请你借助手中的计算机,满怀信心地搜索:
长度为10的等差素数列,其公差最小值是多少?
解题思路:
首先要遍历自然数,然后判断是否为素数,在这个基础下,来从小到大的为其累加一个公差(这个公差是从小到大变化的),每个素数都累加这个公差九次,这样就会产生一组十个数的等差数列,如果该素数始终无法找到合适公差使其构成十个素数的等差数列,那就换下一个素数继续这样的操作,直到第一次遭到合适公差,而这个公差必然满足条件最小的。
代码如下:
#include<iostream>
#include<math.h>
using namespace std;
//判断是否为素数
int prime(int num)
{
int sqrtm = sqrt(num);
int num_is_prime = 1;
for (int i = 2;i <= sqrtm;i++)
{
if (num%i == 0)
{
num_is_prime = 0;
return num_is_prime;
}
}
return num_is_prime;
}
int main()
{
int add = 0;//这里注意,这个变量是来保存i累加后的值,如果不用这个变量而直接用i的话就会导致最外层的循环中i的值也随累加变化而导致错误
for (int i = 2;i < 10000;i++)//从首元素开始检查是否为素数
{
if (prime(i))
{
//公差
for (int j = 2;j < 5000;j++)
{
add = i;
for (int k = 0;k <9;k++)//判断累加了九次的数是否还是素数,这里注意,题目是求长度为十的等差数列,所以这里就只需要累加九次就可以了
{
add += j;//累加
if (!prime(add))
{
break;//结束这个循环
}
}
if (prime(add))
{
cout << j;//这里输出的必然是符合条件的最小公差
return 0;
}
}
}
}
}