{프로젝트 오일러/Project Euler} 7. 10001번째 소수

한국어/Hackerrank - 한국어 버전과 문제가 다를 수 있습니다. 채점은 Hackerrank를 추천합니다.

1 <= 입력개수 <= 10^3, 1 <= 입력값 <= 10^4

limit = 200000
primes = list(range(limit))
primes[0], primes[1] = 0, 0
for i in range(2, limit):
    if primes[i]:
        for j in range(i+i, limit, i):
            primes[j] = 0
primes = tuple(prime for prime in primes if prime)
for _ in range(int(input())):
    print(primes[int(input())-1])

이 문제는 미리 소수들을 구해놓지 않으면 매번 n번까지의 소수를 구하는 작업을 반복해야하기 때문에 자칫 시간초과가 나올 수 있는 문제입니다.

그렇기 때문에 에라토스테네스의 체 방식을 이용해 먼저 소수를 구합니다.

에라토스테네스의 체는 어떤 소수를 제외한 그 소수의 모든 배수를 없애는 방식으로 2의 경우 4부터 모든 짝수를, 3의 경우 9부터(6은 이미 2의 배수에서 삭제) 모든 3의 배수를 삭제합니다.

그런데 에라토스테네스의 체 방식은 걸러내는 방식이기 때문에 먼저 리스트의 크기를 정해주어야 합니다. 

이건 먼저 10배 정도로 해보고 안되면 범위를 증가시키는 것을 추천드립니다.

그렇게 소수를 구하고 나면 소수를 제외한 나머지 수들은 없앤다음 (n-1)번째 인덱스를 출력하면 됩니다.