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

-코드

from math import sqrt
n = 10 ** 7
sieve = [True] * n
m = int(sqrt(n))
for i in range(2, m + 1):
    if sieve[i]:
        for j in range(i + i, n, i):
            sieve[j] = False
arr = [i for i in range(2, n) if sieve[i]]
num = int(input())
print(arr[num - 1])

예전에 풀었던 소수 문제를 참고하려 했었는데 그 문제들은 범위가 주어져 쉽게 구할 수 있지만 이 문제는 범위가 주어진 것이 아니라 몇 번째가 소수인지를 구하는 문제여서 그 방법으로 불가능하였습니다.

그래서 분류를 보니 에라토스테네스의 체라는 것이 있어서 검색을 해보니 소수인 값이 나오면 그 소수의 배수들을 지우는 식으로 제거하여 다른 배열에 True값이 존재하는 부분을 따로 뽑아서 다른 배열에 저장하는 방식이라는 것을 알게 되었습니다.

그래서 기본 틀을 알게 되어서 그것을 이용하여 해결하였으나 범위가 문제라 범위를 몇 번 시도해보니 75점 95점 등등이 나오고 100 점이 나오지 않아서 찾아보니 8백만 이상을 넣어주어야 하는 것을 알게 되어 해결하였습니다.