[python] 에라토스테네스의 체를 이용한 소수 구하기

오늘은 특정 범위 내의 소수를 구하는 데 사용되는 효율적인 알고리즘인 에라토스테네스의 체를 구현해보겠습니다.

 

에라토스테네스의 체란?

에라토스테네스의 체는 고대 그리스 수학자 에라토스테네스가 발견한 소수를 찾는 방법으로, 특정 범위 내의 소수를 효과적으로 구할 수 있는 알고리즘입니다. 에라토스테네스의 체는 미리 정해진 범위 내의 소수를 찾기 위해 해당 범위의 모든 정수를 대상으로 반복적으로 소수의 배수를 제거하는 방법으로 작동합니다.

 

에라토스테네스의 체 작동 원리

에라토스테네스의 체는 다음과 같은 과정을 거칩니다.

1. 주어진 범위의 모든 정수에 대해 소수 여부를 저장할 배열(예: prime[])을 생성합니다.

    초기에는 모든 수를 소수라고 가정하고 배열을 True로 초기화합니다.

     0과 1은 소수가 아니므로 배열의 해당 위치를 False로 설정합니다.
2. 2부터 시작하여 주어진 범위의 제곱근까지 반복하면서 소수를 찾습니다.
3. 현재 수가 소수라면 (배열의 값이 True인 경우), 그 수의 배수들은 소수가 아니므로 해당 배수들의 배열 위치를 False로      설정합니다.

    이를 통해 소수의 배수들을 제거합니다.
4. 반복이 끝나면 배열에서 True인 값을 가지는 인덱스가 소수입니다.

 

def sieve_of_eratosthenes(n):

 

    prime = [True] * (n + 1)

 

    prime[0], prime[1] = False, False

    for p in range(2, int(n**0.5) + 1):

 

        if prime[p]:

 

            for i in range(p * p, n + 1, p):

 

                prime[i] = False

               

 

    return [num for num in range(n + 1) if prime[num]]

 

n = int(input("숫자(n)를 입력하시오(n까지의 소수): "))

 

primes = sieve_of_eratosthenes(n)

 

print(f"{n}까지의 소수: {primes}")

sieve_of_eratosthenes( ) 함수는 주어진 범위 내의 소수를 반환하는 함수입니다.

 

 

<실행결과>

숫자(n)를 입력하시오(n까지의 소수): 50
50까지의 소수: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]