2013年8月31日

UVa 1213 - Sum of Different Primes

#include <cstdio>

const int SIZE = 1121;
bool notP[SIZE];
int p[SIZE], N;

int main() {
  notP[0] = notP[1] = true;
  for (int i = 2; i < SIZE; i++) {
    if (!notP[i]) {
      p[N++] = i;
      for (int j = i + i; j < SIZE; j += i) {
        notP[j] = true;
      }
    }
  }
  int dp[SIZE][15] = {1};
  for (int i = 0; i < N; i++) {
    for (int k = 14; k; k--) {
      for (int j = p[i]; j < SIZE; j++) {
        dp[j][k] += dp[j - p[i]][k - 1];
      }
    }
  }
  int n, k;
  while (scanf("%d%d", &n, &k) && n) {
    printf("%d\n", dp[n][k]);
  }
  return 0;
}

沒有留言:

張貼留言