에라토스테네스의 체 (소수 판별 알고리즘)

에라토스테네스의 체는 소수를 판별하는 알고리즘이다. 

2 이상의 수에 대해 소수를 판별할 때 사용할 수 있다. 어떻게 하는지 단계별로 알아보자면 다음과 같다.

1. 2부터 소수를 구하고자 하는 구간의 수를 나열한다.
2. 2는 소수이므로 2는 남기고 2의 배수를 모두 지운다
3. 3도 소수이므로 3은 남기고 3의 배수를 모두 지운다.
4. 이렇게 수를 증가시켜가며 지워지지 않은 수들에 대해 자기자신만 남기고 그의 배수들은 지우는 과정을 반복하면 지정한 구간의 소수들을 구할 수 있다. 지워지지 않은 숫자들이 바로 소수이다.

이때 2부터 N까지 구간의 소수를 구한다고 하면 우리는 $int(\sqrt N) + 1$까지만 확인해보면 된다. 예를 들어 2부터 120까지의 소수를 판별한다고 하면 $120 < 11^2$ 이므로 11까지만 위의 과정을 반복하고 2~120 사이에 지워지지 않은 숫자들이 그 구간에 있는 소수들이다.

 

파이썬으로 코드를 구현하면 다음과 같다.

# 에라토스테네스의 체
def primeNum(n):
    num_arr = [True] * (n+1)
    for i in range(2, int(n ** 0.5) + 1):
        if num_arr[i]:  # i가 소수라면
            for j in range(i * 2, n, i):    # 자기자신은 제외하고 배수들 지움
                num_arr[j] = False
    return [i for i in range(2, n + 1) if num_arr[i]]

 

[참고]

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