페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#1232

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

문제

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

 

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

 

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


입력

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


출력

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


예제1

입력
73
출력
6

예제2

입력
1512
출력
7

예제3

입력
107
출력
9

출처

COCI 2008/2009 contest2 2

역링크