[파이썬]프로젝트 오일러 #7

소수를 크기 순으로 나열하면 2, 3, 5, 7, 11, 13, ... 과 같이 됩니다.

이 때 10,001번째의 소수를 구하세요.

n = 2**20
primes = [] #소수를 담을 list
table = [False, False] + [True]*(n-1)

for i in range(2, n+1):
    if table[i]:
        primes.append(i)
        for j in range(2*i, n+1, i):
            table[j] = False

print(primes[10000]) #10001번째 값을 꺼낸다.

소수를 구하는 방법은 프로젝트 오일러 5번 문제에 사용했던 table을 만들고 소수의 배수를 하나씩 False로 지워나가는 방식을 사용하였다. 

 

문제점이 있다면 에라토스테네스의 체를 사용하기 위해 맨처음 n을 충분히 큰 수로 먼저 지정해주었는데, 그 만큼 메모리가 비효율적으로 쓰인다.

 

답: 104743