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

题目分析：

哦摩西罗伊，第一次看见不用提交完全代码的题。意思就是强制写函数，其实这种形式还好，但是这道题有点东西。。。

思路大概是：打表1000以内的质数，用 b [1000] 是 0 还是 1 来标记这个数是否为质数（起码我这么做感觉舒适）

然后对每个质数作为数列的第一个数， d （公差）从 1 开始变化来看，暴力枚举所有长度为 n 的等差数列，用 k 来记录长度是否到达，每个等差数列，如果该等差数列的每一项都是素数（用 b 数组值是否为 1 来判断），则 sum++ ，返回时返回 sum 。

1000以内的素数共168个，打表的时候 a[0] 随便输入一个数就好。

值得一提的是，题中的 n 和 m 和代码中的是反着的。

以下是完整代码，抄作业是不对的哟~

#include<stdio.h>
int f(int m,int n)
{
	int a[200]={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,3
73,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,50
3,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,9
67,971,977,983,991,997};
	int i,j,k,d,sum=0;
	int b[1001];
	for(i=1;i<=1000;i++)
		b[i]=0;
	for(i=1;i<=168;i++)
		b[a[i]]=1;
	d=1;
	for(i=1;i<=169-m;i++)
	{
		d=1;
		while(d<=1000)
		{
			k=0;
			j=a[i];
			while(b[j]==1 && j<=n)
			{
				if(k<m)
					k++;
				if(k==m)
				{
					sum++;
					break;
				}
				j += d;
			}
			d++;
		}
	}
	return sum;
}
int main()
{
    int n,m,t;
    while(scanf("%d%d",&m,&n)!=EOF)
    {
        t=f(m,n);
        printf("%d\n",t);
    }
    return 0;
}