PKU 3132 Sum of Different Primes

http://poj.org/problem?id=3132
二つの数字n,kが与えられる。この時、k個の異なる素数の和でnを表す組み合わせはいくつあるかを求めるというような問題。

ずっとあまり分かっていなかった問題。
素数を1つずつ、使う個数が多いほうから埋めていけば、ダブりがなくいけるようです。

int dp[20][1200];
bool pr[1121];
int npr[1121],pos;

main(){
  pr[0]=pr[1]=true;
  for(int i=2;i<1121;i++){
    if(pr[i])continue;
    for(int j=i*2;j<1121;j+=i)pr[j]=true;
  }
  rep(i,1121)if(!pr[i])npr[pos++]=i;

  dp[0][0]=1;
  rep(p,pos){
    for(int k=14;k;k--)
      for(int i=npr[p];i<1121;i++)dp[k][i]+=dp[k-1][i-npr[p]];
  }
  int n,k;
  while(cin>>n>>k,n|k)cout<<dp[k][n]<<endl;
}