COCI 2008/2009 contest2 2- 에라토스테네스의 체 > 문제은행 : 정보올림피아드&알고리즘



1232 : 에라토스테네스의 체

제한시간
1000 ms   
메모리제한
64 MB   
해결횟수
202 회   
시도횟수
319 회   

문제

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

 

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

 

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


입력형식

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


출력형식

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


입력 예

7 3

출력 예

6

입력 예

15 12

출력 예

7

입력 예

10 7

출력 예

9


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010-2019 jungol. All right reserved.

TOP