目录

一、题目描述

二、解题思路

整体思路:

细分每个实现步骤:

步骤1先满足必要条件素数,需要判断数是不是素数

步骤2判断是否存在10个素数且公差为 d ,怎样方便每个 d 的判断呢?

步骤3遍历素数时,如何判断素数之间是否满足等差数列的关系?

步骤4注意限制条件,长度为10的等差素数数列,如何应用呢?

步骤5节省程序的执行时间,如果找到满足条件的公差的首项,可以不用继续判断,直接跳出。

步骤6题意找到第一个满足条件的公差即最小的公差,不必继续遍历查找满足十个等差素数数列的公差,

三、完整代码实现:

运行结果:210

自己理解,如有错误,欢迎指正!如有更好解法,留在评论区,互相学习!


一、题目描述

本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。

2,3,5,7,11,13,….2,3,5,7,11,13,….是素数序列。 类似:7,37,67,97,127,1577,37,67,97,127,157这样完全由素数组成的等差数列,叫等差素数数列

上边的数列公差为30,长度为6。

2004年,格林与华人陶哲轩合作证明了:存在任意长度的素数等差数列。 这是数论领域一项惊人的成果!

有这一理论为基础,请你借助手中的计算机,满怀信心地搜索:

长度为10的等差素数列,其公差最小值是多少?

运行限制

  • 最大运行时间:1s
  • 最大运行内存: 128M

二、解题思路

有题意知:必要条件必须是素数,等差素数数列长度为10,且公差最小

整体思路:

因公差最小,可让公差d逐增,每个 d 都需要判断是否符合长度为10的素数数列。

细分每个实现步骤:

步骤1、先满足必要条件素数,需要判断数是不是素数

int include(int i)   //定义一个函数用于判断素数{int k=0;for(k=2;k<i;k++){if(i%k==0)return 0;}return 1;       //是素数返回1}

步骤2、判断是否存在10个素数且公差为 d ,怎样方便每个 d 的判断呢?

如果每次判断d的同时再从一个个数中判断是否是素数,再查找是否存在这样10个数,那可就太麻烦了。

解决方法:可以用一个数组存放素数,那么在判断公差 d 时只需遍历素数数组,只要从中找到10个数满足条件就可。

for(i=2;i<2500;i++)     //定义一个大的数组存放素数 { if(include(i)==1)    利用函数将素数存放到数组中 {    arr[m]=i;    m++;              //确定存放素数的下标,便于遍历且节省时间} }

步骤3、遍历素数时,如何判断素数之间是否满足等差数列的关系?

1、从等差公式(an=a1+(n-1)*d)着手,遍历判断时,需要知道四个值:首项a1,未知项an,an与a1之间的关系是(n-1)*d。

2、然后实践:需要确定首项a1,已知d,再次遍历a1之后的素数,根据关系判断是否满足长度10个值,

for(i=0;i<m;i++)     //确定遍历的首项   {       for(int j=i+1;j<m;j++)     //遍历首项后的素数是否符合 { if(arr[j]==arr[i]+k*d)  // 找一个满足的首项后的素数               {               }}   }

步骤4、注意限制条件,长度为10的等差素数数列,如何应用呢?

限制条件,应用于知道首项,从遍历首项之后的素数中再找到9个数即可

for(i=0;i<m;i++)    { for(k=1;k<10;k++)      //限制等差数组的长度 { for(int j=i+1;j<m;j++) //此循环的目的是只要找到一个符合的素数即可     { if(arr[j]==arr[i]+k*d)    {  break;   //符合条件后跳出循环,继续找下一个数,避免继续遍历之后的素数耗费时间       } }             }         }

注意:思考一个问题?

上述新加的限制条件,确实限制遍历的次数,但是如果k=1时遍历arr[ j ],却没有找到一个满足的数,那么按照上述程序,会继续查找k=2的符合条件的数,这样有必要吗?

等差数列依次增加,没有第二个满足的素数,此时要变了,更换首项,继续判断是否有满足k=1的数。

for(i=0;i<m;i++)     //确定遍历的首项{ for(k=1;k<10;k++)      { int temp=k;        //定义一个中间变量存放k for(int j=i+1;j<m;j++)      { if(arr[j]==arr[i]+k*d)     temp++;       //如果找到一个数满足,temp++;         break;              }}if(temp==k)    //temp==k的条件是没有找到这个数break;         //跳出循环,更换首项,继续查找。             }         }

步骤5、节省程序的执行时间,如果找到满足条件的公差的首项,可以不用继续判断,直接跳出。

    for(i=0;i<m;i++)     { for(k=1;k<10;k++)       { int temp=k;         for(int j=i+1;j<m;j++)      { if(arr[j]==arr[i]+k*d)     temp++;            break;              }}if(temp==k)break;}if(k==9)  //如果找到第十个数,break;    //跳出循环,不必继续遍历}

步骤6,题意找到第一个满足条件的公差即最小的公差,不必继续遍历查找满足十个等差素数数列的公差,

 while(k<9)        //第一个公差满足条件,直接跳出循环,不用遍历下一个d               {    d++;                  for(i=0;i<m;i++)     { for(k=1;k<10;k++)       { int temp=k;         for(int j=i+1;j<m;j++)      { if(arr[j]==arr[i]+k*d)     temp++;            break;              }}if(temp==k)break;}if(k==9)break;} }

三、完整代码实现:

#includeint include(int i)   {int k=0;for(k=2;k<i;k++){if(i%k==0)return 0;}return 1;       }main(){ int i=0,d=0,m=0; int k=1; int arr[2500]={0}; for(i=2;i<2500;i++)      { if(include(i)==1) {    arr[m]=i;    m++;              } } while(k<9)               {    d++;                  for(i=0;i<m;i++)     { for(k=1;k<10;k++)       { int temp=k;         for(int j=i+1;j<m;j++)      { if(arr[j]==arr[i]+k*d)                      {     temp++;              break;              }}if(temp==k)break;}if(k==9)break;} } printf("%d",d);}

运行结果:210

自己理解,如有错误,欢迎指正!如有更好解法,留在评论区,互相学习!