[python] 소수 찾기 - 에라토스테네스의 체

파이썬으로 소수찾기 by 에라토스테네스의 체

소수를 찾는 방법 중 가장 효율적인 것으로 유명한 방법이 바로 "에라토스테네스의 체" 이다.

그 방법은 다음과 같다.

찾고자 하는 수(n) 까지 True로 채운 리스트를 생성 한 후 2를 제외한 2의 배수, 3을 제외한 3의 배수, 5를 제외한 5의 배수, ... sqrt(n)의 배수는 모두 False로 바꾼다.

결국, 2~n까지 숫자들 중 True인 숫자들이 소수가 된다.

파이썬에서 에라토스테네스의 체 코드는 다음과 같다.

def prime_list(n):
    # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
    sieve = [True] * n
 
    # n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사
    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if sieve[i] == True:           # i가 소수인 경우 
            for j in range(i+i, n, i): # i이후 i의 배수들을 False 판정
                sieve[j] = False
 
    # 소수 목록 산출
    return [i for i in range(2, n) if sieve[i] == True]

>>> prime_list(1)

Out[76]: []

>>> prime_list(10)

Out[77]: [2, 3, 5, 7]

>>> prime_list(20)

Out[78]: [2, 3, 5, 7, 11, 13, 17, 19]