728x90
문제
에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다.
이 알고리즘은 다음과 같다.
1. 2부터 N까지 모든 정수를 적는다.
2. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.
3. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.
4. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.
N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오.
https://www.acmicpc.net/problem/2960
입력
첫째 줄에 N과 K가 주어진다. (1 ≤ K < N, max(1, K) < N ≤ 1000)
출력
첫째 줄에 K번째 지워진 수를 출력한다.
예제
# input
7 3
# output
6
# input
15 12
# output
7문제 풀이
# 입력 받기
N, K = map(int, input().split())
L = [True] * (N+1)
cnt = 0
for i in range(2, N+1):
for j in range(i, N+1, i):
# P를 지우지 않았다면 P를 지우고 배수 순서대로 지움 (지움 표시: False)
if L[j] == True:
L[j] = False
cnt += 1
# K번째 지우는 수 출력
if cnt == K:
print(j)파이썬을 독학하시는 분들에게 도움이 되길 바라며,
혹 더 좋은 방법이 있거나 오류가 있다면 편하게 말씀 부탁드립니다.
728x90
