COCI 2008/2009, Contest #2

Task RESETO

The sieve of Eratosthenes is a famous algorithm to find all prime numbers up to N. The algorithm is:

  1. Write down all integers between 2 and N, inclusive.
  2. Find the smallest number not already crossed out and call it P; P is prime.
  3. Cross out P and all its multiples that aren't already crossed out.
  4. If not all numbers have been crossed out, go to step 2.
Write a program that, given N and K, finds the K-th integer to be crossed out.

Input

The integers N and K (2 ≤ K < N ≤ 1000).

Output

Output the K-th number to be crossed out.

Examples

Input

7 3

Output

6

Input

15 12

Output

7

Input

10 7

Output

9

In the third example, we cross out, in order, the numbers 2, 4, 6, 8, 10, 3, 9, 5 and 7. The seventh number is 9.

All Submissions
Best Solutions


Point Value: 5
Time Limit: 2.00s
Memory Limit: 16M
Added: Nov 21, 2008

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

i dont really get wat to cross out...

its completely clear.
2. Find the smallest number not already crossed out and call it P; P is prime.
3. Cross out P and all its multiples that aren't already crossed out.

tip: ppl get annoyed if u type liek this.

thnx
late reply
LOLZ

what's wrong with my program?

You forgot a semicolon.

It helps us debug if you indent your code.

Yes. That's exactly what's wrong.
BTW, you don't always have to copy codes from PEG. Try making codes of your own, following what they taught you with the original code.

Would there be the possibility of their being no number for the output, because the crossing out part reaches N before K?

~helios

No. As a general principle, you may assume that if the problem statement says nothing about what to do in case some pathological condition arises, then it never actually does arise in the test data.

Can sm1 plss tell me watz wrong wid my program

On six of the eight test cases, you get error 200 (division by zero). The only way this could possibly have occurred is that you mod by s at some point when s is zero. And since s starts at 1 and only increments, it must have been incremented so many times that it wrapped around to zero. This means you probably have an infinite loop. Work on that. Also, again, keep the texting language to a minimum. I'm not going to ban anyone for improper spelling and grammar, but I'm going to keep reminding people until they get annoyed enough to stop.