题目如下:
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;
                    }
            }
        }
    }    

    }
Last modification:April 3rd, 2020 at 06:32 pm
如果觉得我的文章对你有用,请随意赞赏