poj 2739

打一个素数表，发现10000以内的素数个数在1300个之内，直接暴力即可。
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #include<string>
 6 #include<queue>
 7 #include<algorithm>
 8 #include<map>
 9 #include<iomanip>
10 #include<climits>
11 #include<string.h>
12 #include<numeric>
13 #include<cmath>
14 #include<stdlib.h>
15 #include<vector>
16 #include<stack>
17 #include<set>
18 #define INF 1e7
19 #define MAXN 100010
20 #define maxn 1000010
21 #define Mod 1000007
22 #define N 1010
23 using namespace std;
24 typedef long long LL;
25 
26 int prime[11000];
27 int vis[11000];
28 void run()
29 {
30     int k = 1;
31     for (int i = 2; i <= 10000; ++i)
32         if (!vis[i]) {
33             prime[k++] = i;
34             for (int j = i*i; j <= 10000; j += i)
35                 vis[j] = 1;
36         }
37     /*for (int i = 1; i < 1300; ++i)
38         cout << prime[i] << " ";
39     cout << endl;*/
40 }
41 
42 int n;
43 int cnt;
44 
45 void deal(int tmp)
46 {
47     for (int i = 1; i < 1300 && prime[i]; ++i) {
48         int left = tmp;
49         if (tmp < prime[i]) continue;
50         for (int j = i ; j < 1300 && prime[j]; ++j) {
51             left -= prime[j];
52             if (left < 0) break;
53             if (left == 0) cnt++;
54         }
55         
56     }
57 }
58 
59 int main()
60 {
61     run();
62     while (cin >> n,n) {
63         cnt = 0;
64         deal(n);
65         printf("%d
",cnt);
66     }
67     return 0;
68 }