Note: This article is available in Chinese only. 本文暂无英文版本。
View original
一开始迷之wa… 先找出素数下标的上界就可以A… 然后纠结了２０分钟．．． 然后发现是预处理的素数少了一个素数．． 我预处理是处理到＜１０００５的素数．．． 最大数１００００,而超过１００００的第一个素数是１０００７ 这样判断终止条件就会死循环… sad
1/*************************************************************************
2 > File Name: code/poj/2739.cpp
3 > Author: 111qqz
4 > Email: rkz2013@126.com
5 > Created Time: 2015年09月25日 星期五 01时32分43秒
6 ************************************************************************/
7#include<iostream>
8#include<iomanip>
9#include<cstdio>
10#include<algorithm>
11#include<cmath>
12#include<cstring>
13#include<string>
14#include<map>
15#include<set>
16#include<queue>
17#include<vector>
18#include<stack>
19#include<cctype>
20#define y1 hust111qqz
21#define yn hez111qqz
22#define j1 cute111qqz
23#define ms(a,x) memset(a,x,sizeof(a))
24#define lr dying111qqz
25using namespace std;
26#define For(i, n) for (int i=0;i<int(n);++i)
27typedef long long LL;
28typedef double DB;
29const int inf = 0x3f3f3f3f;
30int pri[10005];
31int n ;
32int mx;
33bool prime ( int n)
34{
35 if (n<=3) return true;
36 for ( int i = 2 ; i*i<= n ; i++)
37 {
38 if (n%i==0) return false;
39 }
40 return true;
41}
42void solve()
43{
44 int head = 1;
45 int tail = 1;
46 int sum = 0 ;
47 int ans = 0 ;
48 while (pri[tail]<=n)
49 {
50 cout<<"asd"<<endl;
51 sum = sum + pri[tail];
52 if (sum>=n)
53 {
54 while (sum>n)
55 {
56 sum = sum - pri[head];
57 head++;
58 }
59 if (sum==n)
60 {
61 ans++;
62 }
63 }
64 tail++;
65 }
66 printf("%d\n",ans);
67}
68int main()
69{
70 #ifndef ONLINE_JUDGE
71 // freopen("in.txt","r",stdin);
72 #endif
73 int cnt = 0 ;
74 for ( int i = 2 ; i <= 10005 ; i++)
75 {
76 if (prime(i))
77 {
78 cnt++;
79 pri[cnt] = i ;
80// if (i>10000) cout<<i<<endl;
81 }
82 }
83 while (scanf("%d",&n)!=EOF&&n)
84 {
85 solve();
86 }
87 #ifndef ONLINE_JUDGE
88 fclose(stdin);
89 #endif
90 return 0;
91}