문제1701--에라토스테네스의 체

1701: 에라토스테네스의 체

[만든사람 : ]
시간제한 : 1.000 sec  메모리제한 : 128 MB  제출 : 14  맞은 사람 : 5

제출  

문제 설명

에라토스테네스의 체는 $$N$$까지의 모든 소수들을 찾는 유명한 알고리즘이다.
이 알고리즘은 다음과 같다 : 
  1. $$2$$와 $$N$$ 사이의 모든 정수를 적는다.
  2. 아직 지워지지 않은 가장 작은 숫자를 찾아 $$P$$라고 한다. $$P$$는 소수이다.
  3. $$P$$와 아직 지워지지 않은 $$P$$의 배수를 순서대로 지운다.
  4. 모든 숫자가 지워지지 않은 경우 2번 단계로 이동한다.
$$N$$과 $$K$$가 주어졌을 때, $$K$$번째 지워지는 정수를 구하는 프로그램을 작성하시오.

입력 설명

첫째 줄에는 $$N$$과 $$K$$가 주어진다. $$(2 ≤ K < N ≤ 1000)$$

출력 설명

$$K$$번째 지워지는 숫자를 출력한다.

입력 예시1 Copy

7 3

출력 예시1 Copy

6

입력 예시2 Copy

15 12

출력 예시2 Copy

7

입력 예시3 Copy

10 7

출력 예시3 Copy

9

도움

예시3에서 숫자 2, 4, 6, 8, 10, 3, 9, 5, 7 순서대로 지워진다. 7번째 지워지는 숫자는 9이다.

출처/분류

COCI