에라토스테네스의 체
면접 대비시간 제한1초메모리 제한128 MB
에라토스테네스의 체를 그대로 시뮬레이션해서 K번째로 제거되는 수를 구하는 문제입니다.
문제
에라토스테네스의 체는 (N) 이하의 모든 소수를 찾는 대표적인 알고리즘이다. 이 문제에서는 체에서 수가 지워지는 순서를 그대로 따라간다.
알고리즘은 다음과 같다.
- 2부터 (N)까지의 모든 정수를 적는다.
- 아직 지워지지 않은 수 중 가장 작은 수를 찾는다. 이 수를 (P)라고 하며, (P)는 소수이다.
- (P)를 지우고, 아직 지워지지 않은 (P)의 배수를 작은 것부터 차례대로 지운다.
- 아직 지워지지 않은 수가 남아 있다면 2번 단계로 돌아간다.
(N)과 (K)가 주어졌을 때, 위 과정에서 (K)번째로 지워지는 수를 구하라.
입력
첫째 줄에 두 정수 (N)과 (K)가 주어진다. (1 \le K < N \le 1000)
출력
첫째 줄에 (K)번째로 지워진 수를 출력한다.