UVa - 1213 - Sum of Different Primes

#include <bits/stdc++.h>
using namespace std;

vector <int> Primes;
int Prime[1160], dp[1133][17][193];
int N;

void sieve(){
    int sqr = sqrt(1156);
    for(int i = 2; i <= sqr; i++){
        if(!Prime[i])
        for(int j = i*i; j <= 1156; j += i){
            Prime[j] = 1;
        }
    }
}

int sum_dif_prime(int n, int k, int ind){
    if(!k || n <= 0 || Primes[ind] > N){
        if(!k && !n)return 1;
        return 0;
    }
    if(n > 0 && !k)return 0;
    if(dp[n][k][ind] != -1)return dp[n][k][ind];
    dp[n][k][ind] = sum_dif_prime(n-Primes[ind], k-1, ind+1) + sum_dif_prime(n, k, ind+1);
    return dp[n][k][ind];
}

int main(){
    sieve();
    for(int i = 2; i <= 1156; i++)if(!Prime[i])Primes.push_back(i);
    int K;
    while(cin >> N >> K){
        if(!N && !K)break;
        memset(dp, -1, sizeof(dp));
        int ans = sum_dif_prime(N, K, 0);
        cout << ans << endl;
    }
    return 0;
}