POJ 2739 Sum of Consecutive Prime Numbers 难度:0

题目链接:http://poj.org/problem?id=2739

#include <cstdio>
#include <cstring>
using namespace std;
int method[10001][1300];
int dp[10001];
bool isntprime[10001];
int heap[1300],cnt;
void calprime(){
    method[2][0]=1;
    dp[2]++;
    heap[cnt++]=2;
    for(int i=3;i<10001;i+=2){
        if(!isntprime[i]){
            heap[cnt]=i;
            method[i][cnt++]=1;dp[i]++;
            for(int j=3;i*j<10001;j+=2){
                isntprime[i*j]=true;
            }
        }
    }
}
void caldp(){
    for(int i=2;i<10001;i++){
        for(int j=0;j<cnt;j++){
            if(method[i][j]!=0){
                if(j<cnt-1&&i+heap[j+1]<10001){
                    method[i+heap[j+1]][j+1]+=method[i][j];
                    dp[i+heap[j+1]]+=method[i][j];
                }
            }
        }
    }
}
int main(){
    calprime();
    caldp();
    int n;
    while(scanf("%d",&n)==1&&n){
        printf("%d
",dp[n]);
    }
    return 0;
}