7. 10001st prime

projecteuler.net/problem=7

Problem 7 - Project Euler

 

문제는 다음과 같습니다.

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10 001st prime number?

 

10001번째 소수를 구하는 문제입니다.

 

소수를 구하는 방법은 여러가지 방법이 있습니다만, 저는 에라토스테네스의 체를 이용하여 문제를 해결하였습니다.

코드는 아래의 위키피디아에 잘 나와 있으므로 활용하시면 좋을 것 같습니다.

ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

 

위의 링크를 활용하여 작성한 코드는 아래와 같습니다.

 

import math

# sieve of eratosthenes
def makePnumArr(n) :
    a = [True] * n

    print(len(a))
    max_len = math.ceil(math.sqrt(n))

    for i in range(2, max_len) :
        if a[i] :
            for j in range(i+i, n, i) :
                a[j] = False

    
    return [i for i in range(2, n) if a[i]]



n = 500000
arr = makePnumArr(n)

print(len(arr))
print(arr[10000])