3132 Sum of Different Primes

原文

時間制限:5000ミリ秒
メモリ制限:65536KB

問題

正整数は異なる素数の和として、いくつかの方法で表されるかもしれない。今、2つの正整数n,kが与えられたとき、k個の異なる素数の和としてnを表す方法の数を求めなければならない。ここでは、素数を足す順序を変えただけのものは、同一視する。たとえば、8は3+5、5+3として表されるが、これらは同一視する。n=24,k=3のとき、2+3+19と2+5+17として表されるので、答えは2である。この他に、表し方はない。n=24,k=2のときは、5+19、7+17、11+13として表されるので、答えは3である。n=2,k=1のときは、和が2であるのは「2」だけなので、答えは1である。n=1,k=1のときは、1は素数ではないので、答えは0である。n=4,k=2のときは、和が4である2つの異なる素数が存在しないので、答えは0である。与えられたn,kに関して、k個の異なる素数の和としてnを表す方法の数を求めるプログラムを作成せよ。

入力

入力の各行には、2つの正整数n,k(n <= 1120, k <= 14)が書かれている。入力の終端には、2つの0が書かれている。

出力

出力は、いくつかの行から成る。各行には、入力の対応する行のnとkに関して、k個の異なる素数の和としてnを表す方法の数を表す1つの非負整数を出力せよ。答えは、2^31を越えないと仮定してよい。

入力の例

24 3
24 2
2 1
1 1
4 2
18 3
17 1
17 3
17 4
100 5
1000 10
1120 14
0 0

出力の例

2
3
1
0
0
2
1
0
1
55
200102899
2079324314

出典

Japan 2006