VM7WC '15 #1 Gold - JHK

View as PDF
Submit solution
Points: 10
Time limit: 2.5s
Memory limit: 256M
Author:
thorthugnasty
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.

Hint

It would be helpful to know the Sieve of Eratosthenes.

Sample Input

5 1

Sample Output

3

Comments


  • 1
    FatalEagle  commented on Jan. 9, 2015, 4:44 a.m. ← edit 2

    If your solutions TLE on Python 3, you can try submitting in PyPy 3 (which is a faster interpreter for Python 3).


  • 2
    Butane  commented on Jan. 8, 2015, 10:43 p.m. ← edited

    Is there a reason that my second submission for this problem was removed? I had solved it a while back


    • 0
      thorthugnasty  commented on Jan. 9, 2015, 8:23 p.m. ← edited

      This is an in school contest and although outside participation is accepted we don't like to see our top ranks filled by non-Massey students. Plus it's not a very serious competition so I didn't think it would be a big deal. Sorry if this caused any tears or emotional outbursts. Note: I don't think I'll delete outside submissions anymore because that would mean work.


      • 5
        FatalEagle  commented on Jan. 9, 2015, 8:37 p.m. ← edited

        While removing contest participations or contest submission records is within the rights of the contest organizer to a reasonable extent, deleting submissions is a misuse of privilege. To remove a user from the rankings, simply remove their contest participation instead of deleting submissions, or make it clear the unofficial participants should join some amount of time after the contest begins.


    • 4
      quantum  commented on Jan. 8, 2015, 11:08 p.m. ← edit 2

      Found missing submission #27250 inside logs. thorthugnasty apparently deleted it, ask him for the reason.

      https://i.imgur.com/3oowLt1.png