[Python] 백준/BOJ 15965번: K번째 소수 (Silver 2)

💻 Problem

문제 보러 가기

 

한결이를 도와 k번째 소수를 알려주자.

소수의 정의는 다음과 같다.

2 이상의 자연수 N이 1과 N을 제외하고 어떤 자연수로도 나누어 떨어지지 않을 때 소수라고 한다.

 

💡 Approach

25점 코드

import sys
input = sys.stdin.readline

def is_prime(target):
    global k
    
    for i in range(2, int(target ** 0.5) + 1):
        if target % i == 0:
            return False

    k -= 1
    return True

k = int(input())
i = 1

while k > 0:
    i += 1
    is_prime(i)

print(i)

반복문으로 소수 판별을 하면 서브태스크 2까지만 통과할 수 있다.

위 코드의 시간복잡도는 약 O(k √k)이다.

 

서브태스크 2에서 k의 최댓값은 4 * 10 ^ 4, 100점에서 k의 최댓값은 5 * 10^5이다.

k √k에 대입해 보면 전자는 1억을 초과하지 않고, 후자는 1억을 초과한다.

그래서 위 코드는 25점짜리이다.

100점에서 k의 최댓값이 통과하려면 n log log n의 시간복잡도를 가진 에토스테네스의 체로 풀어야 한다.

 

✏️ Solution

import sys
input = sys.stdin.readline

k = int(input())
n = 7368787

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

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

        # k번째로 지워진 수 찾기
        if k == 0: 
            print(i)
            break

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

에라토스테네스의 체가 동작하는 방식은 다음과 같다.

1. 체를 [False, False] + [True] * (n + 1)로 초기화한다.
2. 2부터 n까지 검사한다.
   1. sieve[i]가 지워지지 않았다면, i는 소수이다.
   2. i의 배수를 sieve에서 모두 지운다.

n은 k의 최댓값인 500,000번째 소수를 구해 지정했다.