POJ - 2739 Sum of Consecutive Prime Numbers

题目大意：

给定一个数，让其由若干个连续的素数相加（包括本身，如果本身也是素数的话）的组合方法有几种

　　

分析：

素数表+取尺法。显然需要先打一个素数表，个人用的是埃氏筛选法，再用尺取法来算区间和是不是等于t就
行了

　　

code:

#define debug
#include<stdio.h>
#include<math.h>
#include<cmath>
#include<queue>
#include<stack>
#include<string>
#include<cstring>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<vector>
#include<functional>
#include<iomanip>
#include<map>
#include<set>
#define pb push_back
#define dbg(x) cout<<#x<<" = "<<(x)<<endl;
#define lson l,m,rt<<1
#define cmm(x) cout<<"("<<(x)<<")";
#define rson m+1,r,rt<<1|1
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll>PLL;
typedef pair<int,ll>Pil;
typedef pair<ll,int>Pli;
const ll INF = 0x3f3f3f3f;
const ll inf=0x7fffffff;
const double eps=1e-8;
const int maxn =1000000;
const int N = 510;
const ll mod=1e9+7;
const ll MOD=10007;
//------
//define
int a[maxn];
bool is_prime[maxn];
int cnt;
void setPrime(){
	memset(is_prime,1,sizeof(is_prime));
	for(int i=2;i<=10000;i++){
		if(!is_prime[i])continue;
		a[cnt++]=i;
		for(int j=1;j*i<=10000;j++)is_prime[j*i]=0;
	}
}
//solve
void solve() {
	int t;
	setPrime();
	while(cin>>t&&t){
		int sum=0,count=0,l=0,r=0;
		for(;;){
			while(a[r]<=t&&sum<t){
				sum+=a[r++];
			}
			if(sum==t)count++;
			sum-=a[l++];
			if(sum<=0)break;
		}
		cout<<count<<endl;
	} 
}
int main() {
	ios_base::sync_with_stdio(false);
#ifdef debug
	freopen("in.txt", "r", stdin);
//	freopen("out.txt","w",stdout);
#endif
	cin.tie(0);
	cout.tie(0);
	solve();
	return 0;
}