아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

에라토스테네스의 체

면접 대비

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

요약
설명된 에라토스테네스 체 과정을 그대로 구현해 각 테스트 케이스의 K번째로 지워지는 수를 출력합니다.
난이도

쉬움10점 중 2점

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

문제

에라토스테네스의 체는 NN 이하의 소수를 모두 찾는 알고리즘이다. 절차는 다음과 같다.

  1. 22부터 NN까지의 정수를 모두 적는다.
  2. 아직 지워지지 않은 수 중 가장 작은 수를 찾아 PP라고 한다. PP는 소수이다.
  3. PP와 PP의 배수 중 아직 지워지지 않은 수를 작은 것부터 차례대로 지운다.
  4. 지워지지 않은 수가 남아 있으면 2번으로 돌아간다.

NN과 KK가 주어질 때 KK번째로 지워지는 수를 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어진다. 각 줄에 정수 NN과 KK가 공백으로 구분되어 주어진다. (2≤K<N≤10002 \le K < N \le 1000)

입력의 끝까지 모든 줄을 처리한다.

출력

각 테스트 케이스마다 KK번째로 지워진 수를 한 줄에 하나씩 출력한다.

예제4

  1. 예제 1

    입력
    7 3
    15 12
    10 7
    
    예상 출력
    6
    7
    9
  2. 예제 2

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

    입력
    11 2
    11 3
    11 4
    11 5
    11 6
    11 7
    11 8
    11 9
    11 10
    
    예상 출력
    4
    6
    8
    10
    3
    9
    5
    7
    11
  4. 예제 4

    입력
    4 2
    4 3
    5 2
    5 3
    5 4
    6 5
    
    예상 출력
    4
    3
    4
    3
    5
    5