[파이썬/python] 백준 - 15965 K번째 소수

문제

https://www.acmicpc.net/problem/15965

---

문제 설명

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

 

---

풀이

문제에서 구하는 K의 최댓 값은 500,000이며 이를 구하면 7,368,787이다.

그럼 500,000번째소수를 찾기 위해서는 약 1~7,000,000까지의 수를 모두 탐색해야 한다.

def is_prime(N):
    flag = True
    for i in range(2, N):
        if N % i == 0:
            flag = False
            break

기본적인 소수 찾기 알고리즘의 시간복잡도는 $O(N)$이다.

2부터 N까지의 수를 모두 탐색하며 소수를 판별한다.

해당 문제에서는 7,000,000까지의 수를 모두 탐색하므로 총 $O(N*2)$의 시간복잡도가 소요되며,

문제의 제한시간인 1초$(약 O(100,000,000))$를 초과하게 된다.

 

def is_prime(N):
    flag = True
    for i in range(2, N//2 + 1):
        if N % i == 0:
            flag = False
            break

시간복잡도를 더 간략하게 하기 위해서 N//2로 나눈 값까지 탐색한다.

$N = 100$이라고 하면 N을 나눌 수 있는 값의 최댓 값은 N의 절반인 50이다. 따라서 N의 절반까지만 탐색 해도 소수임을 판별할 수 있다.

$N//2$ 방식으로 계산하면 시간복잡도는 $O(N*N/2)$이며 이 또한 $O(10^8)$을 초과한다.

 

def is_prime(N):
    flag = True
    for i in range(2, N//2 + 1):
        if N % i == 0:
            flag = False
            break

$N$을 최대 $\sqrt N$까지 탐색한다면 시간복잡도를 더 줄일 수 있다.

$N = 160$일 때 N의 약수는 $1,2,4,5,8,10,16,20,32,40,80,160$이다.

160의 약수 중 160을 나눌 수 있는 값은 $1,2,4,5,8,10$이며, $\sqrt 160=$ 12.xx... 즉 12를 넘지 않는 것을 볼 수 있다.

160을 나눌 수 있는 수는 $\sqrt N$을 넘지 않기 때문에 $\sqrt N$까지만 탐색을 해도 소수 판별이 가능하다.

시간복잡도는 $O(N*\sqrt N)$으로 이 또한 $O(10^8)$을 초과한다.

 

def is_prime(N):
    arr=[i for _ in range(2,N+1)]
    for i in range(2, N+1):
        for j in range(i*2, N, i)
        	arr[j] = 0
    return prime

따라서 에라토스테네스의 체를 사용한다.

2부터 N까지 자신의 배수를 체에 거르듯이 전부 0으로 바꾼다.그럼 배열의 값이 1인 수는 소수가 된다.

에라토스테네스의 체의 시간복잡도는 $O(N*log{log_N})$이다.

따라서 매우 큰 소수를 찾을 때 유용하다.

문제에 적용하면 $O(28 * 10^6) = O(10^7)$정도로 시간초과를 해결할 수 있다.

 

 

1. 에라토스테네스의 체를 이용하여 8,000,000까지의 소수를 모두 구한다.
2. 입력받은 K번째 소수를 출력한다.

---

코드

import sys
import math
input = sys.stdin.readline

MAX = int(1e6)*8

def make_prime():
    arr = [i for i in range(MAX)]
    arr[1] = 0
    for i in range(2, math.isqrt(MAX)):
        for j in range(i*2, MAX, i):
            arr[j] = 0
    primes = []
    for prime in arr:
        if prime:
            primes.append(prime)
    return primes

N = int(input())

prime = make_prime()
print(prime[N-1])

---

시간복잡도

• 에라토스테네스의 체의 시간복잡도는 $O(N*log{log_N})$
• MAX = 8,000,000이므로  약 $O(28 * 10^6) = O(10^7)$