急！！！！！！！！C语言难题高手请进。

Question

在小于10的素数中有3、5、7组成的等差数列，在小于30的素数中有11、17、23、29组成的等差数列。试找出区间[100,1000]内的素数构成的最大等差数列（即等差数列包含的素数个数最多）并打印输出。

Answer 1

抛砖引玉，我用最简单的最低效的思路实现：

/* 在小于10的素数中有3、5、7组成的等差数列，
* 在小于30的素数中有11、17、23、29组成的等差数列。
* 试找出区间[100,1000]内的素数构成的最大等差数列（即等差数列包含的素数个数最多）并打印输出。
*/

#include <stdio.h>

#define MIN_NUMBER 100
#define MAX_NUMBER 1000

// 判断数字是否为素数．　若不是素数，返回0.
int is_prime(int iTest)
{
if (2 > iTest || iTest % 2 == 0)
{
return 0;
}

int i = 0;
for (i = 3; i < iTest; i += 2)
{
if (iTest % i == 0)
{
return 0;
}
}
return 1;
}

//
int get_prime_seq(int firstP, int iStep)
{
int iLen = 0;
for (iLen = 0; iLen < MAX_NUMBER - MIN_NUMBER; iLen++)
{
if (0 == is_prime(firstP + iStep * iLen))
{
return iLen;
}
}
return 0;
}

// 返回firstP开始的"最大素数列表"的长度
int get_max_prime_seq(int firstP, int *pStep)
{
int iLen = 0;
int iStep = 1;
int iTmpStep = 1;
for (iTmpStep = 1; iTmpStep < MAX_NUMBER - MIN_NUMBER; iTmpStep++)
{
int iTmpLen = get_prime_seq(firstP, iTmpStep);
if (iTmpLen > iLen)
{
iLen = iTmpLen;
iStep = iTmpStep;
}
}
*pStep = iStep;
return iLen;
}

int main(int argc, char* argv[])
{
int iP = MIN_NUMBER; // 记录"最大素数列表"的第一个素数
int iLen = 0; // 记录"最大素数列表"的长度
int iStep = 1; // 记录"最大素数列表"的公差

int i = 0;

int iTmpP = 0; // 枚举p
for (iTmpP = MIN_NUMBER; iTmpP < MAX_NUMBER; iTmpP++)
{
int iTmpStep = 0; // 临时step
int iTmpLen = 0; // 临时len
iTmpLen = get_max_prime_seq(iTmpP, &iTmpStep);
if (iTmpLen > iLen)
{
iP = iTmpP;
iLen = iTmpLen;
iStep = iTmpStep;
}
}
for (i = 0; i < iLen; i++)
{
printf("%d\n", iP + iStep * i);
}
return 0;
}

没有经过严格调试，结果为:
199
409
619
829
1039
1249
1459
1669
1879
2089

Answer 2

算法：
先求出100-1000之内所有素数的个数，记录下最大max和最小的值min，其中间的差值
是最大等差用于for循环for(int i=0;i<=max-min;i++)，然后创建一个结构体，其中记录起始值和末尾值还有差值从1开始(开始时记录起始值和差值)，一旦有不符合条件的（填充末尾值和数组长度），则该结构体填充完毕（和上一个比较其数组长度）选取最大的作为当前记录，然后则从新开始，差值加1，依次循环
（BUG 默认起始值是从最小的素数开始的）
改进：创建max-min个上述结构体，分别记录下不同差值的数组最大长度，然后比较不同差值下的最大数组长度
编程这东西学到最后拼的是思维，而不是编码，但如果编码都不过关，就有些不好了本回答被网友采纳

Answer 3

#include<stdio.h>
#include<math.h>
void main()
{
int i,j,d,k=0,m=1,num,sh[450]={0},dc[450]={0},dcmax,MAX,Maxnum=2,MD;
for(i=101;i<1000;i=i+2)
{
for(j=2;j<=sqrt(i);j++)
if(i%j==0)break;
if(j>sqrt(i)){sh[k++]=i;}
}
printf("区间[100,1000]内的素数:\n");
for(k=0;sh[k];k++)
printf("%5d",sh[k]);
for(i=0;i<k-1;i++)
for(j=i+1;j<k;j++)
{
dcmax=sh[j];
d=sh[j]-sh[i];
num=2;
for(m=j+1;m<k;m++)
{
if(sh[m]-sh[i]==num*d){num++;dcmax=sh[m];}
else if(sh[m]-sh[i]>num*d)
{
if(num>Maxnum)
{
Maxnum=num;
MAX=dcmax;
MD=d;
}

break;
}

}
}
printf("\n[100,1000]内的素数构成的最大等差数列：");
for(i=Maxnum-1;i>=0;i--)
printf("%5d",MAX-MD*i);
printf("\n");
}