[Python] 백준/BOJ 2960번: 에라토스테네스의 체 (Silver 4)

💻 Problem

문제 보러 가기

 

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

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

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

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

 

✏️ Solution 1

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
num = [i for i in range(2, n + 1)]

while num:
    p = num.pop(0)
    k -= 1

    if k == 0:
        print(p)
        break

    for i in range(p * 2, n + 1, p):
        if i in num:
            num.pop(num.index(i))
            k -= 1

            if k == 0:
                print(i)
                exit(0)

문제에서 주어진 1~4를 직관적으로 푼 방법이다.

 

✏️ Solution 2

import sys
input = sys.stdin.readline

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

# 2부터 n까지의 숫자가 지워졌는지 여부를 나타내는 체
sieve = [True] * (n + 1)

for i in range(2, n + 1):
    # 아직 지워지지 않은 경우
    if sieve[i]:
        # i의 배수를 모두 제거
        for j in range(i, n + 1, i):
            if sieve[j]:
                sieve[j] = False
                k -= 1
                
                # k번째로 지워진 수 찾기
                if k == 0: 
                    print(j)
                    exit()

에라토스테네스의 체로 푼 코드이다.

정확히는 sieve의 index 0, 1의 값은 False여야 한다.

에라토스테네스의 체의 시간복잡도는 O(n log log n)이다.