POJ2739(Japan2005) 連續素數和 conprime 解題報告

 連續素數和   題目來源：Japan 2005 （POJ2739）


連結：http://poj.org/problem?id=2739


【問題描述】

一些正整數可以表示成一個或多個連續素數和的形式。那麼一個正整數可以表示成多少種連續素數和的形式呢？例如： 53 有 2 種連續素數和的形式分別是 5+7+11+13+17 和 53. 正整數 41 有 3 種連續素數和的形式： 2+3+5+7+11+13,11+13+17 和 41. 整數 3 只有一種連續素數和的形式就是 3 。 20 就不能表示成連續素數的和。

你的任務就是找出整數 N 能表示成的連續素數和的種數。

【輸入格式】

* 每行一個正整數 N(2<=N<=10000) ，表示你要處理的數。當 N=0 時輸入結束。

【輸出格式】

* 對於每一個整數 N ，你要輸出它能表示成連續素數和的種數。

【輸入輸出樣例】

輸入

2

3

17

41

20

666

12

53

0

輸出

1

1

2

3

0

0

1

2

【分析】

COGS上寫的是貪心策略，但是我想了半天也不知道該如何貪，最後只好寫枚舉了。最後竟然還過了，只不過有點慢。

由於N<=10000，所以程序應先初始化出2～10000之間的素數表。

（我第一次提交時WA了，50分，原因是我只初始化了2～5003之間的素數表，畢竟題目中說“連續”嘛，至少應該有兩個加數～其實，在測試數據中，1個數也叫做『連續』）

然後暴力枚舉，你懂的～

【我的代碼】

裸代碼RawCode

C++语言: Codee#25466

01 /*
02 *Problem: POJ2739 conprime
03 *Author: Yee-fan Zhu
04 *GTalk: zyfworks@gmail.com
05 *Source: Japan2005
06 */
07 #include <cstdio>
08 #include <cstdlib>
09 using namespace std;
10 const int MAXN=1500;
11 const int MAXP=10000;
12 int P[MAXN+100];
13 int prime=0;
14 void Prime()
15 {
16     P[++prime]=2;
17     for(int i=3;i<=MAXP;i+=2)
18     {
19         bool flag=true;
20         for(int j=2;j<=i/2;j++)
21         {
22             if(i%j==0)
23             {
24                 flag=false;
25                 break;
26             }
27         }
28         if(flag)
29         {
30             P[++prime]=i;
31         }
32     }
33     /*
34     for(int i=1;i<=prime;i++)
35         printf("%d\n",P[i]);
36     Test if the Primes are Correct
37     */
38 }
39
40 int main()
41 {
42     freopen("conprime.in","r",stdin);
43     freopen("conprime.out","w",stdout);
44     Prime();
45     int N;
46     scanf("%d\n",&N);
47     int Res,ans;
48     while(N)
49     {
50         Res=0;
51         for(int i=1;i<=prime;i++)
52         {
53             ans=0;
54             for(int j=i;j<=prime;j++)
55             {
56                 ans+=P[j];
57                 if(ans>N)
58                     break;
59                 if(ans==N)
60                 {
61                     Res++;
62                     break;
63                 }
64             }
65         }
66         printf("%d\n",Res);
67         scanf("%d\n",&N);
68     }
69     return 0;
70 }