UVA solution 1213 - Sum of Different Primes

#include <bits/stdc++.h>
#define pb push_back
#define MAX 10006
#define mod 1000000009
#define read freopen("input.txt","r",stdin);
#define base 10
using namespace std;
typedef long long ll;
typedef unsigned long long llu;
bool mark[MAX];
vector<int>prime,p;
int target,cnt,n;
ll dp[500][20][1200];
void sieve()
{
    for(int i=3; i<=sqrt(MAX); i+=2)
    {
        if(!mark[i]) for(int j=i*i; j<MAX; j+=i) mark[j]=true;
    }

    prime.pb(2);
    for(int i=3; i<MAX; i+=2) if(!mark[i]) prime.pb(i);

}

ll call(int i,ll sum,int c)
{

    if(sum>target) return 0;
    if(c==cnt)
    {
        if(sum==target) return 1;
        else return 0;
    }
    if(i>=n) return 0;
    if(dp[i][c][sum]!=-1) return dp[i][c][sum];

    return  dp[i][c][sum]=call(i+1,sum+p[i],c+1)+call(i+1,sum,c);

}


int main()
{
    // read;
    sieve();  // easy knapsack
    //cout<<prime.size()<<endl;
    // for(int i=0;i<5;i++) cout<<prime[i]<<endl;
    while(scanf("%d %d",&target,&cnt)&& target &&cnt)
    {
        memset(dp,-1,sizeof(dp));
        p.clear();
        for(int i=0; prime[i]<=target; i++) p.pb(prime[i]);
        n=p.size();
        printf("%lld\n",call(0,0,0));

    }





    return 0;
}