에라토스테네스의 체
소수(prime number)란?
1과 자기 자신을 제외한 다른 어떤 수로도 나누어지지 않는 자연수이다. 예를 들어, 2, 3, 5, 7, 11 등은 소수이다.
일반적으로 소수를 판별하는 방법 중 하나는 특정 수가 소수인지 하나씩 확인하는 O(√N) 방식이다. 예를 들어, 어떤 수 xx가 소수인지 판별하려면 1부터 xx까지 모든 수를 나누어보는 대신, √x까지만 확인하면 충분하므로 O(√N)의 시간 복잡도를 갖는다.
하지만 N까지의 모든 소수를 찾을 때 이 방식을 그대로 적용하면, 각 숫자마다 O(√N) 연산을 수행해야 하므로 전체적으로 O(N√N)의 시간 복잡도가 발생한다.
이 때문에 여러 개의 소수를 한 번에 찾기에는 비효율적이며, 보다 빠르게 소수를 구하기 위해 에라토스테네스의 체 같은 최적화된 알고리즘이 사용된다.
에라토스테네스의 체는 고대 그리스의 수학자 에라토스테네스(Eratosthenes) 가 고안한 소수(prime number)를 찾는 알고리즘이다. 이 방법은 2부터 N까지의 모든 소수를 빠르게 구하는 알고리즘으로, 특정 범위 내의 소수를 찾는 데 효과적이다.
알고리즘 원리
소수는 자신과 1을 제외한 다른 어떤 수로도 나누어지지 않는 수이므로, 어떤 수가 소수라면 그 수의 배수는 모두 소수가 아니다. 이를 기반으로 가장 작은 소수부터 시작하여 해당 수의 배수를 제거해 나가면 소수만 남게 된다.
에라토스테네스의 체는 다음과 같은 절차를 따른다:
- 2부터 원하는 범위(N)까지의 모든 수를 나열
- 가장 작은 수(2)부터 시작하여 해당 수의 배수를 지운다 (자기 자신은 제외)
- 남아있는 수 중에서 다음으로 작은 수를 선택하고 해당 수의 배수를 지운다
- 이를 반복하면 소수만 남게 된다
이 방법을 사용하면 모든 수에 대해 나눗셈 연산을 수행하는 대신 배수를 제거하는 방식으로 불필요한 연산을 줄일 수 있어 매우 효율적이다.
예제
초기 상태: 2부터 30까지의 수를 나열한다. (N = 30)
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 27 28 29 30
1. 2의 배수를 제거 (2는 소수이므로 남긴다)
2 3 - 5 - 7 - 9 - 11 - 13 - 15 - 17 - 19 - 21 - 23 - 25 - 27 - 29 -
2. 3의 배수를 제거
2 3 - 5 - 7 - - - 11 - 13 - - - 17 - 19 - - - 23 - - - 29 -
3. 5의 배수를 제거
2 3 - 5 - 7 - - - 11 - 13 - - - 17 - 19 - - - 23 - - - 29 -
남은 수: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 (소수)
구현
에라토스테네스의 체는 다양한 방식으로 구현할 수 있으며, 보통 사용하는 자료구조에 따라 성능과 메모리 사용량이 달라진다. 대표적으로 다음과 같은 방식들이 있다.
| 구현 방식 | 시간 복잡도 | 공간 복잡도 | 특징 |
| 리스트(List) 활용 | O(N * log(log N)) | O(N) | 가장 기본적인 방식, 직관적이고 빠름 |
| 집합(Set) 활용 | O(N * log(log N)) | O(N) | 집합 연산 활용으로 가독성이 좋지만, 리스트보다 속도가 느릴 수 있음 |
| 비트마스크(Bitmask) 활용 | O(N * log(log N)) | O(N / 8) | 메모리 사용량이 적으며 대규모 데이터 처리에 유리함 |
에라토스테네스의 체의 시간 복잡도는 O(N log log N) 으로 표현되는데, 이는 다음과 같이 유도된다:
- 각 소수 에 대해, 그 배수들을 지우는 작업이 이루어진다.
- 어떤 수 가 지워지는 횟수는, 해당 수의 최소 소인수를 기준으로 한다.
- 즉, 한 수는 여러 번 지워질 필요 없이 한 번만 지워진다.
- 전체적으로 소수의 개수에 비례한 연산이 수행되며, 이는 N / log N 개 정도이다.
- 따라서, 최종적으로 O(N log log N) 으로 표현된다.
이는 일반적인 소수 판별 방법인 O(N√N) 보다 훨씬 빠른 성능을 제공한다.
또한, 에라토스테네스의 체의 공간 복잡도는 O(N) 이며, 이는 소수 여부를 저장하기 위해 사용되는 리스트 또는 비트 배열이 N 크기의 메모리를 차지하기 때문이다.
코드 1 : 리스트
가장 일반적으로 사용되는 방법으로, 불리언 배열을 사용해 소수를 판별한다. 구현이 직관적이고 빠르며, 추가적인 라이브러리가 필요하지 않아 널리 사용된다.
def sieve_of_eratosthenes(n):
is_prime = [True] * (n + 1)
is_prime[0], is_prime[1] = False, False
for i in range(2, int(n**0.5) + 1):
if is_prime[i]:
for j in range(i * i, n + 1, i):
is_prime[j] = False
return [i for i in range(2, n + 1) if is_prime[i]]
코드 2 : 집합 자료구조
배열 대신 집합(set)을 활용하여 배수를 제거하는 방식이다. 코드가 간결하지만, 내부적으로 해시 연산이 발생하여 리스트보다 연산 비용이 증가할 수 있다.
def sieve_with_set(n):
primes = set(range(2, n + 1))
for i in range(2, int(n**0.5) + 1):
if i in primes:
primes -= set(range(i * i, n + 1, i))
return sorted(primes)
코드 3 : 비트마스크
비트 배열을 사용하여 메모리 사용량을 줄이는 방식이다. 리스트 대비 메모리를 1/8 수준으로 절약할 수 있지만, 비트 연산이 필요하며 bitarray 같은 라이브러리를 사용해야 한다.
from bitarray import bitarray
def sieve_with_bitmask(n):
is_prime = bitarray(n + 1)
is_prime.setall(True)
is_prime[0], is_prime[1] = False, False
for i in range(2, int(n**0.5) + 1):
if is_prime[i]:
is_prime[i * i : n + 1 : i] = False
return [i for i in range(2, n + 1) if is_prime[i]]