VM7WC '15 #1 Gold - JHK

View as PDF

Submit solution

Points: 10
Time limit: 2.5s
Memory limit: 256M

Problem type

JHK (whose true name shall not be revealed) is one of Mr. Ing's favourite students. In light of the recent successful defense of the Ingdom, JHK decides to celebrate by preparing for this year's Putnam contest. On week one of his Seven Week Challenge, JHK decides he wants to study prime numbers. Write a program to help him solve the following problem.

Define the Junghoon-value (or the J-value for short) of a positive integer i to be the least number of primes (not necessarily distinct) required to yield a sum of i. For example, the number 8 can be formed using the primes 2,2,2,2 OR 3,5, therefore its J-value is 2. Note: If no combination of primes sum to i, its J-value is undefined.

Help Junghoon JHK find the number of positive integers less than or equal to N (1 \le N \le 7\,000) with J-value of exactly K (1 \le K \le N).

Input Specification

One line containing two space-separated integers N and K.

Output Specification

Print the number of positive integers less than or equal to N with J-value of exactly K.


It would be helpful to know the Sieve of Eratosthenes.

Sample Input

5 1

Sample Output



There are no comments at the moment.