소수 찾기에 최적화된 알고리즘인 에라토스테네스의 체(Sieve of Eratosthenes)에 대해서 알아보겠습니다.
에라토스테네스의 체
에라토스테네스의 체는 고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수(Prime Number)를 찾는 방법입니다.
에라토스테네스는 특정 정수 이하의 모든 소수를 찾기 위해서 소수를 찾는 것이 아니라 소수인 반대인 합성수(Composite Number)를 제거하는 창의적인 접근을 하는데요. 그 알고리즘이 마치 우리가 가루나 액체 등을 분리하기 위해서 체를 사용하는 것과 비슷하여 에라토스테네스의 체(Sieve of Eratosthenes)라고 합니다.
에라토스테네스의 체 알고리즘에서는 정수 n이 주어졌을 때, 우선 2부터 n까지의 모든 수가 소수가 될 수 있다고 가정하고 나열합니다.
예를 들어, 26이 주어졌다면 다음과 같이 체에 숫자가 펼쳐질 것입니다.
{2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26}이제부터 이 숫자들 중에서 합성수를 제거할 건데요.
맨 처음에는 가장 작은 소수인 2를 제외한, 2의 배수를 제거합니다.
{2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26}
- {4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26}
= {2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25}그 다음, 3를 제외한 3의 배수를 체에서 털어냅니다.
{2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25}
- {6, 9, 12, 15, 18, 21, 24}
= {2, 3, 5, 7, 11, 13, 17, 19, 23, 25}4의 배수는 이미 2의 배수를 털어낼 때 모두 털어냈으므로 굳이 다시 털어내봤자 아무 의미가 없을 것입니다.
따라서 5를 제외한 5의 배수를 체에서 털어냅니다.
{2, 3, 5, 7, 11, 13, 17, 19, 23, 25}
- {10, 15, 20, 25}
= {2, 3, 5, 7, 11, 13, 17, 19, 23}우리는 여기서 이제 체에 26 이하의 소수만 남아있는 것을 볼 수 있습니다.
6보다 큰 수에 대해서는 체어서 털어낼 필요가 없는 이유는 26의 제곱근은 약 5.1이기 때문입니다.
n의 제곱근보다 큰 정수 중에서 약수가 있다면, n의 제곱근보다 작은 정수 중에서 100% 그 약수와 짝이 되는 다른 약수가 있습니다.
예를 들어, 18의 제곱근은 약 4.2이고 약수는 1과 자신을 제외하면 다음과 같은데요.
제곱근: 4.2
약수: {2, 3, 6, 9}4.2보다 큰9와 짝이 되는 약수2는4.2보다 작습니다.4.2보다 큰6과 짝이 되는 약수3은4.2보다 작습니다.
이를 통해 우리는 2부터 n - 1이 아니라 n의 제곱근까지만 체를 털어줘도 충분하다는 것을 알 수 있습니다.
배열을 이용한 구현
에라토스테네스의 체는 배열을 이용해서 구현할 수도 있고 집합을 이용해서 구현할 수도 있습니다.
우선 배열(Array)을 이용해서 구현해보면, 우선 n + 1개의 참이 저장되어 있는 배열을 생성합니다.
그 다음, 변수를 2로 초기화하고 n의 제곱근에 다다를 때까지 변수를 1씩 증가시면서 다음 작업을 반복합니다.
- 배열에서 변수의 자리에 참이 저장되어 있는지를 확인합니다.
- 참이 저장되어 있다면, 변수의
2의 배수,3의 배수,4의 배수, … 이렇게 차례로 배열에 거짓으로 저장합니다. - 참이 저장되어 있지 않다면, 이미 이전에 해당 수의 배수가 모두 털어져나갔다는 뜻이므로 그냥 다음 숫자로 넘어갈 수 있습니다.
위 과정을 while 반복문을 통해서 파이썬으로 구현해보겠습니다.
def sieve_of_eratosthenes(n):
is_prime = [True] * (n + 1)
num = 2
while num**2 <= n:
if is_prime[num]:
for composite in range(num**2, n + 1, num):
is_prime[composite] = False
num += 1
return [p for p in range(2, n + 1) if is_prime[p]]for 반복문을 사용하면 좀 더 짧은 코드로 구현이 될 것입니다.
def sieve_of_eratosthenes(n):
is_prime = [True] * (n + 1)
for num in range(2, int(n**0.5) + 1):
if is_prime[num]:
for composite in range(num**2, n + 1, num):
is_prime[composite] = False
return [p for p in range(2, n + 1) if is_prime[p]]집합을 이용한 구현
집합(Set)을 활용하여 에라토스테네스의 체를 구현하면 우리가 사고하는 과정과 좀 더 유사해져서 코드가 좀 더 이해하기 쉬워집니다.
아래와 같이, 합성수를 하나씩 집합에서 제거할 수도 있고요.
def sieve_of_eratosthenes(n):
primes = set(range(2, n + 1))
for num in range(2, int(n**0.5) + 1):
if num in primes:
for composite in range(num * 2, n + 1, num):
primes.discard(composite)
return list(primes)합성수를 집합에 모은 후에 차집합 연산을 해줄 수도 있습니다.
def sieve_of_eratosthenes(n):
primes = set(range(2, n + 1))
for num in range(2, int(n**0.5) + 1):
if num in primes:
primes -= set(range(num * 2, n + 1, num))
return list(primes)복잡도
에라토스테네스의 체 알고리즘의 시간 복잡도는 O(n * log(log n))으로 알려져있는데 분석하기가 좀 어려운 편이라서 추가로 검색해보시기를 추천드립니다.
공간 복잡도 분석은 비교적 간단한데 n과 비례해서 커지는 배열 또는 집합을 사용하기 때문에 O(n)이 되겠습니다.