[백준 2960번] 에라토스테네스의 체 / Python3

문제

에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다.

이 알고리즘은 다음과 같다.

1. 2부터 N까지 모든 정수를 적는다.
2. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.
3. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.
4. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.

N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ K < N, max(2, K) < N ≤ 1000)

출력

첫째 줄에 K번째 지워진 수를 출력한다.

예제 입력 1

10 7

예제 출력 1

9

나의 풀이

해당 문제는 구현 문제로 1,2,3,4번에 해당하는 로직을 코드로 짜주면 되는 간단한 문제였다. 필자는 기존에 에라토스테네스의 체를 이 같은 방법으로 작성하지 않았지만 이러한 방법도 있다는 것을 알 수 있는 문제였다.

풀이로는 다음과 같다.

1. 2부터 n까지 담긴 리스트를 만들어준다.
2. 리스트의 가장 앞의 값을 pop()연산을 통해 삭제 및 변수에 저장을 한다.
3. 위에서 저장한 변수에 같은 값을 계속 더해가며 더해진 값이 배열에 존재한다면 지우고 지워지는 숫자들의 리스트에 삽입한다.
4. 3번의 과정이 끝나고 아직 1번에서 만든 배열에 값이 남아있다면 2,3번의 과정을 반복한다.

코드

# 2960번 에라토스테네스의 체

n, k = map(int, input().split())

eratos = [i for i in range(2, n+1)]

delete_nums = []
while eratos:
    delete_num = eratos.pop(0)
    delete_nums.append(delete_num)

    tmp = delete_num
    while tmp <= n:
        if tmp in eratos:
            eratos.remove(tmp)
            delete_nums.append(tmp)
        tmp += delete_num

print(delete_nums[k-1])