Problem 1269 : Sum of Different Primes

Problem D: Sum of Different Primes
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1269

• 問題概要

異なる素数を組み合わせて、その数が何通り作れますか？

• 解法

メモ化探索？
大きい時にわからなければ小さい問題にわければいい！
みたいな感じ。
今どこまでの素数までつかったか、あとのこりいくつ素数がつかえるか、あと合計いくらにすればいいか。　を　
引数にして再帰。

• ソース

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<sstream>
#include<cassert>
#include<queue>
#include<stack>

#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)
#define ALL(C)     (C).begin(),(C).end()
#define pb         push_back
#define mp         make_pair
#define vint       vector<int>
#define FOR(it,o)  for(__typeof((o).begin()) it=(o).begin(); it!=(o).end(); ++it)
#define lli	    long long int
#define ld	    long double

#define N 1121
#define P 188
#define K 15

using namespace std;
bool t[N]; 
vector<int> p; 
int c[N][P][K];

int dp(int sum, int now, int num){
  if(sum == 0 && num == 0)return 1;
  if(num == 0)return 0;
  if(sum == 0)return 0;
  if(now == P)return 0; 
  if(c[sum][now][num] >= 0)return c[sum][now][num];
  int ans = 0;
  REP(i, now, P){
    if(p[i] > sum)break;
    ans += dp(sum-p[i], i+1, num-1);
  }
  c[sum][now][num] = ans;
  return ans;
}



main(){
  fill(t, t+N, true);
  rep(i, N){
    rep(j, P){
      rep(k, K){
	c[i][j][k] = -1;
      }
    }
  }
  t[0] = t[1] = false;
  rep(i, N){
    if(!t[i])continue;
    p.pb(i);
    for(int j=2; i*j < N; j++){
      t[i*j] = false;
    }
  }

  int n, k;
  while(cin >> n >> k){
    if(n+k == 0)break;
    
    cout << dp(n, 0, k) << endl;
  }
  
}