n個(gè)素?cái)?shù)構(gòu)成等差數(shù)列

---

Time Limit: 1 Sec??Memory Limit: 128 MB?? 64bit IO Format: %lld

Description

?有n個(gè)素?cái)?shù)（均小于m）可以構(gòu)成一個(gè)等差數(shù)列。請(qǐng)編寫(xiě)程序根據(jù)給定的n和m，統(tǒng)計(jì)出滿(mǎn)足條件的解有多少種。

例如，n=3，m=10；即在1到10的范圍內(nèi)有3個(gè)素?cái)?shù)構(gòu)成等差數(shù)列的情況有幾組解，很顯然3，5，7是一組解，也是唯一的一組。

提示：main函數(shù)已經(jīng)給出（如下所示），提交時(shí)不必提交下面的代碼，只需要提交你自己添加的代碼。

#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

?包含多組測(cè)試數(shù)據(jù)，每組測(cè)試數(shù)據(jù)占一行，每行2個(gè)正整數(shù)，分別代表n和m，其中n大于等于3且小于等于10，m小于等于1000。

Output

?每組測(cè)試數(shù)據(jù)輸出占一行，每行輸出一個(gè)整數(shù)，即滿(mǎn)足條件的解的組數(shù)。

Sample Input

3 10

?

Sample Output

1

---

題目分析：

哦摩西羅伊，第一次看見(jiàn)不用提交完全代碼的題。意思就是強(qiáng)制寫(xiě)函數(shù)，其實(shí)這種形式還好，但是這道題有點(diǎn)東西。。。

思路大概是：打表1000以?xún)?nèi)的質(zhì)數(shù)，用 b [1000] 是 0 還是 1 來(lái)標(biāo)記這個(gè)數(shù)是否為質(zhì)數(shù)（起碼我這么做感覺(jué)舒適）

然后對(duì)每個(gè)質(zhì)數(shù)作為數(shù)列的第一個(gè)數(shù)， d （公差）從 1 開(kāi)始變化來(lái)看，暴力枚舉所有長(zhǎng)度為 n 的等差數(shù)列，用 k 來(lái)記錄長(zhǎng)度是否到達(dá)，每個(gè)等差數(shù)列，如果該等差數(shù)列的每一項(xiàng)都是素?cái)?shù)（用 b 數(shù)組值是否為 1 來(lái)判斷），則 sum++ ，返回時(shí)返回 sum 。

1000以?xún)?nèi)的素?cái)?shù)共168個(gè)， 打表的時(shí)候 a[0] 隨便輸入一個(gè)數(shù)就好。

值得一提的是，題中的 n 和 m 和代碼中的是反著的。

以下是完整代碼，抄作業(yè)是不對(duì)的喲~

---

#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;
}

?

總結(jié)

以上是生活随笔為你收集整理的n个素数构成等差数列的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。