Page not loading? Try clicking here.
Placeholder

#1232

에라토스테네스의 체 1s 64MB

Problems

에라토스테네스의 체는 어떤 수 N까지의 소수를 구하는 유명한 알고리즘이다. 그 알고리즘은 아래와 같다.

 

1. 2와 N을 포함하여 그사이의 수들을 차례로 적는다. 2. 지우지 않은 수들 중에서 가장 작은 수를 찾는다. 그 수는 소수이고 그 수를 P라고 하자. 3. P를 지우고 아직 지워지지 않은 P의 배수들을 지운다. 4. 아직 지워지지 않은 수가 있다면 2번으로 돌아가서 다시 시작한다.

 

두수 N과 K가 주어질 때, K번째로 지워지는 정수를 출력하시오.


Input

두수 N과 K의 범위는 2≤K<N≤1,000 이다.


Output

K번째로 지워지는 수를 출력하시오.


Example #1

7 3
6

Example #2

15 12
7

Example #3

10 7
9

Source

COCI 2008/2009 contest2 2

You must sign in to write code.