에라토스테네스의 체

면접 대비

시간 제한1초메모리 제한128 MB

요약
에라토스테네스의 체를 그대로 시뮬레이션해서 K번째로 제거되는 수를 구하는 문제입니다.
난이도

쉬움10점 중 3점

유형
시뮬레이션, 수학
정답자
아직 제출이 없습니다

문제

에라토스테네스의 체는 (N) 이하의 모든 소수를 찾는 대표적인 알고리즘이다. 이 문제에서는 체에서 수가 지워지는 순서를 그대로 따라간다.

알고리즘은 다음과 같다.

  1. 2부터 (N)까지의 모든 정수를 적는다.
  2. 아직 지워지지 않은 수 중 가장 작은 수를 찾는다. 이 수를 (P)라고 하며, (P)는 소수이다.
  3. (P)를 지우고, 아직 지워지지 않은 (P)의 배수를 작은 것부터 차례대로 지운다.
  4. 아직 지워지지 않은 수가 남아 있다면 2번 단계로 돌아간다.

(N)과 (K)가 주어졌을 때, 위 과정에서 (K)번째로 지워지는 수를 구하라.

입력

첫째 줄에 두 정수 (N)과 (K)가 주어진다. (1 \le K < N \le 1000)

출력

첫째 줄에 (K)번째로 지워진 수를 출력한다.

예제3

  1. 예제 1

    입력
    7 3
    
    예상 출력
    6
    
  2. 예제 2

    입력
    15 12
    
    예상 출력
    7
    
  3. 예제 3

    입력
    10 7
    
    예상 출력
    9