에라토스테네스의 체 (소수 구하기)

1과 자기 자신을 약수로 갖는 수를 소수(prime number)라고 한다.

 

prime 넘버를 쉽게 구하기위해 에라토스테네스라는 수학자의 소수구하는 방법을 확인해볼 필요가 있다.

 

https://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

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

def prime_list(n):
    sieve = [True] * n
    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if sieve[i] == True:         
            for j in range(2*i, n, i):
                sieve[j] = False

    return [i for i in range(2, n) if sieve[i] == True]