티스토리 뷰
목차
숫자 중 1과 자기 자신만으로 나누어떨어지는 '소수(Prime Number)'를 찾는 과정은 수학적 난제이자 알고리즘의 단골 소재입니다. 하나의 숫자가 소수인지 판별하는 것은 쉽지만, "1부터 1,000,000 사이의 소수를 모두 찾아라"라는 대량의 요청이 들어온다면 단순 탐색으로는 시간이 너무 오래 걸립니다. 이때 고대 그리스의 학자 에라토스테네스가 고안한 '에라토스테네스의 체(Sieve of Eratosthenes)'는 마치 고운 체로 모래를 걸러내듯 소수가 아닌 수들을 제거하여 소수만을 남기는 경이로운 효율성을 보여줍니다. 본 포스팅에서는 이 알고리즘의 동작 메커니즘과 최적화 기법을 2,500자 이상의 상세한 설명으로 기술하겠습니다.
1. 에라토스테네스의 체: 거름망의 논리적 구조
에라토스테네스의 체는 "어떤 수 $p$가 소수라면, $p$의 배수들은 절대로 소수가 될 수 없다"는 명쾌한 논리에서 출발합니다. 2부터 시작하여 현재 숫자가 아직 지워지지 않았다면(소수라면), 그 숫자의 배수들을 모두 찾아 목록에서 지워나가는 방식입니다. 이미 지워진 숫자는 건너뛰며 탐색 범위를 좁힙니다. 이 과정을 반복하면 체 위에는 지워지지 않은 '순수한 소수'들만 남게 됩니다. 이는 데이터를 일일이 검사하는 대신, 집합 단위로 배제해 나가는 효율적인 필터링 전략입니다.
1-1. 시간 복잡도의 미학: $O(N \log \log N)$
이 알고리즘이 놀라운 이유는 시간 복잡도에 있습니다. 단순하게 각 숫자마다 소수 판별법($O(\sqrt{N})$)을 적용하면 전체 $O(N \sqrt{N})$이 소요되지만, 에라토스테네스의 체는 $O(N \log \log N)$이라는 선형 시간($O(N)$)에 매우 근접한 복잡도를 달성합니다. 이는 $N=1,000,000$일 때 단순 방식은 수억 번의 연산이 필요하지만, 체 방식은 수백만 번의 연산만으로 결과를 도출함을 의미합니다.
2. 알고리즘의 정밀 최적화: 제곱근($\sqrt{N}$) 원리
에라토스테네스의 체를 구현할 때 가장 중요한 최적화 포인트는 탐색의 한계 설정입니다. 어떤 수 $n = a \times b$일 때, $a$와 $b$ 중 적어도 하나는 $\sqrt{n}$보다 작거나 같습니다. 따라서 우리는 $N$까지의 소수를 구할 때, $N$의 제곱근인 $\sqrt{N}$까지만 배수 제거 작업을 수행하면 됩니다. 그 이후의 숫자들은 이미 앞에서 배수가 제거되었거나, 남은 수 자체가 소수임이 보장되기 때문입니다. 이 수학적 통찰은 불필요한 반복문을 절반 이상 줄여주는 핵심 열쇠입니다.
3. 공간 복잡도와 메모리 관리 기법
성능은 뛰어나지만, 탐색 범위 $N$에 비례하는 크기의 배열이 필요하다는 점은 유일한 단점입니다. $N$이 1억을 넘어갈 경우 메모리 점유율이 수백 메가바이트에 달할 수 있습니다. 이를 해결하기 위해 실무에서는 비트마스킹(Bitmasking)을 도입하여 불리언 배열의 각 원소를 1비트로 관리하거나, 짝수를 아예 배제하고 홀수만을 대상으로 체를 돌리는 등의 메모리 절약 기법을 병행합니다.
4. 실무에서의 활용: 난수 생성과 데이터 보안
소수는 현대 보안과 전산 시스템의 핵심입니다.
- 암호 알고리즘: 대규모 소수 생성을 통한 공개키 암호화(RSA) 토대 마련.
- 해시 테이블 최적화: 해시 테이블의 크기를 소수로 설정하여 데이터 충돌(Collision) 최소화.
- 수학적 모델링: 소수 정리를 이용한 데이터 분포 예측 및 난수 생성기의 시드(Seed) 확보.
# 에라토스테네스의 체 고속 구현 (Python)
def sieve(n):
# 0, 1은 소수가 아니므로 False, 나머지는 True 초기화
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
# n의 제곱근까지만 확인
for i in range(2, int(n**0.5) + 1):
if is_prime[i]:
# i가 소수라면 i의 배수들을 제곱부터 시작해 제거
for j in range(i*i, n + 1, i):
is_prime[j] = False
return [i for i, prime in enumerate(is_prime) if prime]
1. 원리: 소수의 배수를 순차적으로 제거하여 남은 소수들을 걸러내는 필터링 기법입니다.
2. 효율: $\sqrt{N}$까지만 검사하여 $O(N \log \log N)$의 압도적인 처리 속도를 달성합니다.
3. 적용: 대량의 소수 목록이 필요한 모든 수치 연산 및 보안 로직의 표준 알고리즘입니다.