Loading [MathJax]/jax/output/HTML-CSS/jax.js
Toggle navigation
자주묻는질문
문제
출처/분류
채점기록
순위
대회
로그인
로그인
회원가입
문제1701--에라토스테네스의 체
1701: 에라토스테네스의 체
[만든사람 :
admin
]
시간제한 :
1.000
sec
메모리제한 :
128 MB
제출 :
14
맞은 사람 :
5
제출
통계
문제 설명
에라토스테네스의 체는
N
까지의 모든 소수들을 찾는 유명한 알고리즘이다.
이 알고리즘은 다음과 같다 :
2
와
N
사이의 모든 정수를 적는다.
아직 지워지지 않은 가장 작은 숫자를 찾아
P
라고 한다.
P
는 소수이다.
P
와 아직 지워지지 않은
P
의 배수를 순서대로 지운다.
모든 숫자가 지워지지 않은 경우 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
제출
C3coding