레이팅 미적용설명
에라토스테네스의 체는 \(N\) 이하의 모든 소수를 찾는 유명한 알고리즘이다. 알고리즘은 다음과 같다:
- \(2\) 이상 \(N\) 이하의 모든 정수를 적는다.
- 아직 지워지지 않은 가장 작은 수를 찾아 \(P\)라고 부른다. \(P\)는 소수이다.
- \(P\)와, 아직 지워지지 않은 그 배수들을 모두 지운다.
- 모든 수가 지워지지 않았다면 2단계로 간다.
\(N\)과 \(K\)가 주어졌을 때, \(K\)번째로 지워지는 정수를 찾는 프로그램을 작성하시오.
제약
입력 형식
정수 \(N\)과 \(K\) (\(2 \le K < N \le 1000\))가 주어진다.
출력 형식
\(K\)번째로 지워지는 수를 출력한다.
서브태스크
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Subtask 1 | 40점 |
예제 1
입력
7 3출력
6예제 2
입력
15 12출력
7예제 3
입력
10 7출력
9설명
We cross out, in order, the numbers 2, 4, 6, 8, 10, 3, 9, 5 and 7. The seventh number is 9.
문제 정보
태그