Loading [MathJax]/jax/output/HTML-CSS/jax.js
문제1701--에라토스테네스의 체

1701: 에라토스테네스의 체

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

제출  

문제 설명

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

입력 설명

첫째 줄에는 NK가 주어진다. (2K<N1000)

출력 설명

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 
C3coding