本文主要是介绍WUSTOJ:n个素数构成等差数列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
WUSTOJ:n个素数构成等差数列
Time Limit: 1 Sec
Memory Limit: 128 MB
64bit IO Format: %lld
Description
有n个素数（均小于m）可以构成一个等差数列。请编写程序根据给定的n和m，统计出满足条件的解有多少种。
例如，n=3，m=10；即在1到10的范围内有3个素数构成等差数列的情况有几组解，很显然3，5，7是一组解，也是唯一的一组。
提示：main函数已经给出（如下所示），提交时不必提交下面的代码，只需要提交你自己添加的代码。
#include<stdio.h>
int main()
{
int n,m,t;
while(scanf("%d%d",&m,&n)!=EOF)
{
t=f(m,n);
printf("%d\n",t);
}
return 0;
}
Input
包含多组测试数据，每组测试数据占一行，每行2个正整数，分别代表n和m，其中n大于等于3且小于等于10，m小于等于1000。
Output
每组测试数据输出占一行，每行输出一个整数，即满足条件的解的组数。
Sample Input
3 10
Sample Output
1
作答
选用C语言作答
分析
- 因为数据有界，首先可以把1000以内的素数进行打表，利用数组存储，节省计算时间。
- 在查找的过程中一定牵扯到遍历的方法，要选取适当的方法减少计算时间。
- 通过查询可知1000以内的素数共有168个，这里我将a[0]=0是为了数组的下标和素数相对应。并且可以得出结论等差数列的公差d最大为997-2=995（以首位素数差当作界点的最大公差）。项数为3，公差最小的等差数列为（3，5，7），此时公差为2。整个过程中满足，2<=d<=995，压缩d的取值区间。
int a[169]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997};
- 利用数组下标表示素数，用（0，1）区分是否为素数
int b[1001];for(i=1;i<=1000;i++)b[i]=0;for(i=1;i<=168;i++)b[a[i]]=1;
- 使用while语句进行状态读取，即‘ 0 ’为非素数，‘ 1 ’为素数，并且沿顺序继续读取下去。同时在扫描素数的时候，可以减少最后一组等差数列判断，即只扫到169-m即可。
- 因为要求的等差数列有项数要求，所以用计数器，我这里用的是count。
- 题目的m，n有点混乱，注意辨析。
源码
int f(int m,int n)
{int a[169]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997};int i;int b[1001];for(i=1;i<=1000;i++)b[i]=0;for(i=1;i<=168;i++)b[a[i]]=1;int j,count,d,sum=0;for(i=1;i<=169-m;i++){d=2;while(d<=995){count=0;j=a[i];while(b[j]==1 && j<=n){if(count<m)count++;if(count==m){sum++;break;}j += d;}d++;}}return sum;
}
ps：在c语言的情况下，这个思路出奇的相同（通过和学长的交流知道）。如果有更好的，不超时的，ac过的代码，欢迎来踹我。
这篇关于WUSTOJ:n个素数构成等差数列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
