에라토스테네스의 체
면접 대비시간 제한1초메모리 제한256 MB
설명된 에라토스테네스 체 과정을 그대로 구현해 각 테스트 케이스의 K번째로 지워지는 수를 출력합니다.
문제
에라토스테네스의 체는 이하의 소수를 모두 찾는 알고리즘이다. 절차는 다음과 같다.
- 부터 까지의 정수를 모두 적는다.
- 아직 지워지지 않은 수 중 가장 작은 수를 찾아 라고 한다. 는 소수이다.
- 와 의 배수 중 아직 지워지지 않은 수를 작은 것부터 차례대로 지운다.
- 지워지지 않은 수가 남아 있으면 2번으로 돌아간다.
과 가 주어질 때 번째로 지워지는 수를 구하는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트 케이스로 이루어진다. 각 줄에 정수 과 가 공백으로 구분되어 주어진다. ()
입력의 끝까지 모든 줄을 처리한다.
출력
각 테스트 케이스마다 번째로 지워진 수를 한 줄에 하나씩 출력한다.