Sum of Different Primes#3498

Sum of Different Primes

1 saniye
64 megabayt
Orta

A positive integer may be expressed as a sum of different prime numbers (primes), in one way or another. Given two positive integers and , you should count the number of ways to express as a sum of different primes. Here, two ways are considered to be the same if they sum up the same set of the primes. For example, can be expressed as 3 + 5 and 5 + 3 but they are not distinguished.

When and are and respectively, the answer is two because there are two sets \{2, 3, 19\} and \{2, 5, 17\} whose sums are equal to . There are no other sets of three primes that sum up to . For n = 24 and k = 2, the answer is three, because there are three sets , and . For n = 2 and k = 1, the answer is one, because there is only one set whose sum is . For n = 1 and k = 1, the answer is zero. As is not a prime, you shouldn't count . For n = 4 and k = 2, the answer is zero, because there are no sets of two different primes whose sums are .

Your job is to write a program that reports the number of such ways for the given and .

Giriş

Each line gives one dataset containing two positive integers (n \leq 1120) and (k \leq 14) separated by a space. The last line contains two zeros and is not processed.

Çıktı

For each test case print in a separate line the number of ways to express as a sum of different primes. You may assume that each answer is less than 2^{31}.

Örnekler

Örnek 1

Loading
Loading