Code: Select all
#include <bits/stdc++.h>
using namespace std;
#define _CRT_SECURE_NO_DEPRECATE
typedef long long ll ;
typedef vector <int> vi ;
typedef pair <int, int> ii ;
typedef vector <ii> vii;
typedef set <int> si ;
typedef map <string,int> msi;
#define REP(i,a,b) \
for (int i = int (a) ; i <= int (b) ; i++) // a to b , i is local
#define TRvi(c,it) \
for (vi::iterator it = (c).begin () ; it != (c).end () ; it++)
#define TRvii(c,it) \
for (vii::iterator it = (c).begin () ;it !=(c).end () ;it++)
#define TRmsi(c,it) \
for (msi::iterator it = (c).begin () ;it != (c).end () ; it++)
#define INF 2000000000 // 2 billion
#define MEMSET_INF 127 // about 2B
#define MEMSET_HALF_INF 63 // about 1B
//memset (dist, MEMSET_INF , sizeof dist) ;//useful to initialise shortest path distance
////memset (dp_memo, -1 ,sizeof dp_memo) ; // useful to initialise Dp memoization table
////memset (arr, 0 ,sizeof arr); //useful to clear array of integers
#define DFS_WHITE -1
#define DFS_BLACK 1
#define DFS_GRAY 2
// project euler : 504458-5s4ADvk3PVARbBTSz7iSgq2XlyLMjcs00BOE0Bme
ll _sieve_size;
bitset<1200> bs; // 10^7 + small extra bits should be enough for most prime related problem
vi arr; //compact list of primes in form of vector <int>
void sieve(ll upperbound) // create a list of primes in [0,....upperbound]
{
_sieve_size=upperbound+1 ; // add 1 to include upperbound;
bs.reset(); // set all numbers to 0
bs.flip(); // set all numbers to 1
bs.set(0,false) ;
bs.set(1,false) ; // except index 0 and 1
for(ll i=2;i<=_sieve_size;i+=1)
{
if(bs.test((size_t)i))
{
//cross out multiples of i starting from i*i !
for(ll j=i*i;j<=_sieve_size;j+=i)
bs.set((size_t)j,false);
arr.push_back((int)i);
}
}
}
int n,k,dp[188][1121][15];
int knapsack(int id,int sum,int taken)
{
if(dp[id][sum][taken]!=-1)
{
return dp[id][sum][taken];
}
else {
if(sum==0)
{
if(taken==k)
return 1;
else return 0;
}
else if(taken==k)
{
if(sum==0)
return 1;
else return 0;
}
else if(id==(int)arr.size())
{
if(sum==0&&taken==k)
{
return 1;
}
else return 0;
}
else if(id+(k-taken)>187)
{
return 0;
}
else if(sum-arr[id]<0)
{
return dp[id][sum][taken]=0;
}
else{
dp[id][sum][taken]=0+knapsack(id+1,sum,taken)+knapsack(id+1,sum-arr[id],taken+1);
return dp[id][sum][taken];
}
}
}
int
main ( int argc, char *argv[] )
{
sieve(1120);
while(scanf("%d%d",&n,&k)==2)
{
if(n==0&&k==0) break;
memset(dp,-1,sizeof dp);
int ans=knapsack(0,n,0);
printf("%d\n",ans);
}
return EXIT_SUCCESS;
} /* ------
