POJ 2739

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 
 8 typedef pair<int,int> pii;
 9 
10 #define maxn 10005
11 
12 int len = 0,len1 = 0,n;
13 int ele[maxn];
14 bool prime[maxn];
15 
16 
17 void init() {
18         for(int i = 2; i <= maxn - 5; ++i) {
19                 prime[i] = i % 2 || i == 2;
20         }
21 
22         for(int i = 2; i * i <= maxn - 5; ++i) {
23                 if(prime[i])
24                 for(int j = i; j * i <= maxn - 5; ++j) prime[j * i] = 0;
25         }
26 
27         for(int i = 2; i <= maxn - 5; ++i) if(prime[i]) ele[len++] = i;
28         //for(int i = 0; i < 10; ++i) printf("%d ",ele[i]);
29 
30 
31 }
32 
33 int main()
34 {
35    // freopen("sw.in","r",stdin);
36     init();
37 
38     while(~scanf("%d",&n) && n) {
39             int s = 0,pos = 0,sum = 0,ans = 0;
40             for(; ele[s] <= n; ++s) {
41                     while(sum < n && pos < len ) {
42                             sum += ele[pos++];
43                     }
44                     if(sum < n) break;
45                     if(sum == n) ++ans;
46                     sum -= ele[s];
47             }
48             printf("%d\n",ans);
49 
50     }
51 
52 
53     return 0;
54 }