[백준 | 파이썬] 2960 : 에라토스테네스의 체

문제

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

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

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

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

입력

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

출력

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

풀이 방법

내림차순으로 숫자 배열을 만들고, 가장 마지막 요소(최솟값)를 pop해준다.

pop()된 원소는 제외 순서를 저장할 리스트에 추가한다.

이제 제거된 원소의 배수들을 숫자배열에서 제거한다.

리스트 표현식을 사용해 p부터 n까지 p 간격으로 이동하면서 배수 배열을 생성한다.

배수 배열 안에서 배수가 숫자배열안에 아직 있으면 지워주고, 지워진 원소를 리스트에 추가해 준다.

리스트에는 제거 순서대로 숫자들이 담긴다. k-1번째 원소를 찾으면 끝

코드

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

arr = [i for i in reversed(range(2, n+1))]
stack = []
while arr:
    p = arr.pop()
    stack.append(p)
    nums = [i for i in range(p, n+1, p)]
    for num in nums:
        if num in arr:
            arr.remove(num)
            stack.append(num)
print(stack[k-1])