Problem Link : https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3654

Solution Idea:

This problem is similar to Uva 10616 – Divisible Group Sums . This one can be solved using knapsack or Coin change. In this problem the objects or coins are prime numbers. So at first we calculate the prime numbers using sieve algorithm in the given range of input.

Then we simply call a dp function and show the ans. In this problem the value of objects or coins is not changing in every cases so we need not to clear the dp array every time. We just calculate the process backwards in dp function.

/*
         +-+ +-+ +-+
         |R| |.| |S|
         +-+ +-+ +-+
 */

#include <bits/stdc++.h>

#define pii             pair <int,int>
#define sc              scanf
#define pf              printf
#define Pi              2*acos(0.0)
#define ms(a,b)         memset(a, b, sizeof(a))
#define pb(a)           push_back(a)
#define MP              make_pair
#define db              double
#define ll              long long
#define EPS             10E-10
#define ff              first
#define ss              second
#define sqr(x)          (x)*(x)
#define D(x)            cout<<#x " = "<<(x)<<endl
#define VI              vector <int>
#define DBG             pf("Hi\n")
#define MOD             100007
#define MAX             10000
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)           (int)a.size()
#define sf(a)           scanf("%d",&a)
#define sfl(a)          scanf("%lld",&a)
#define sff(a,b)        scanf("%d %d",&a,&b)
#define sffl(a,b)       scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)     scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)    scanf("%lld %lld %lld",&a,&b,&c)
#define loop(i,n)       for(int i=0;i<n;i++)
#define REP(i,a,b)      for(int i=a;i<b;i++)
#define TEST_CASE(t)    for(int z=1;z<=t;z++)
#define PRINT_CASE      printf("Case %d: ",z)
#define all(a)          a.begin(),a.end()
#define intlim          2147483648
#define inf             1000000
#define ull             unsigned long long

using namespace std;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/


vector<int> prime;
bool visit[1130];
int n,k;

void sieve()
{
    for(int i=2;i<1130;)
    {
        prime.pb(i);
        for(int j=i+i;j<1130;j+=i)
            visit[j]=1;
        for(++i;;i++) if(visit[i]==0) break;
    }
}

ll dp[195][15][1130];

ll func(int idx, int cnt, int sum)
{
    if(cnt==0)
    {
        if(sum==0) return 1;
        return 0;
    }

    if(idx>=SZ(prime)) return 0;

    ll &ret=dp[idx][cnt][sum];

    if(ret!=-1) return ret;

    int p=0,q=0;

    if(sum-prime[idx]>=0) p=func(idx+1,cnt-1,sum-prime[idx]);
    q=func(idx+1,cnt,sum);

    return ret=p+q;
}


int main()
{
    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);

    sieve();

    ms(dp,-1);

    while(sff(n,k)==2 && (n && k))
    {
        ll ans=func(0,k,n);
        pf("%lld\n",ans);
    }

    return 0;
}