알고리즘 문제나 수학 관련 코딩 테스트에서 빠지지 않고 등장하는 주제가 바로 '소수(Prime Number)'입니다. 소수란 1과 자기 자신만으로 나누어떨어지는 1보다 큰 양의 정수를 말합니다(예: 2, 3, 5, 7, 11...). 숫자 하나가 소수인지 판별하는 건 쉽지만, "1부터 100만까지의 숫자 중 소수를 모두 출력하라"는 문제가 나오면 이야기가 달라집니다. 이때 무식하게 반복문을 돌리면 '시간 초과'의 늪에 빠지게 됩니다. 오늘은 고대 그리스 수학자의 지혜가 담긴, 가장 빠르고 효율적인 소수 판별 알고리즘인 에라토스테네스의 체를 알아보겠습니다.
1. 왜 기본적인 방법은 느릴까? (Brute Force)
가장 단순한 방법은 2부터 N까지 모든 숫자에 대해, 1과 자기 자신 외의 약수가 있는지 일일이 나누어보는 것입니다.
// 비효율적인 방법 O(N^2)
for (i = 2 to 100000) {
for (j = 2 to i-1) {
if (i % j == 0) // 나누어지면 소수가 아님
}
}
이 방식은 숫자가 커질수록 계산량이 기하급수적으로 늘어납니다. 100만 개의 숫자를 검사하려면 수천억 번의 연산이 필요하여 컴퓨터도 멈칫하게 됩니다. 제곱근까지만 검사한다고 해도($O(N\sqrt{N})$) 대량의 소수를 구하기엔 여전히 느립니다.
2. 에라토스테네스의 체: 배수를 지워나가라
기원전 200년경, 에라토스테네스는 소수를 "찾는" 것이 아니라, 소수가 아닌 것들을 "걸러내는(Sifting)" 역발상적인 방법을 고안했습니다. 마치 체(Sieve)로 가루를 걸러내듯, 합성수(소수가 아닌 수)들을 지워나가는 방식입니다.
2-1. 알고리즘 동작 과정
1부터 50까지의 소수를 구한다고 가정해 봅시다. 1. 초기화: 2부터 50까지 모든 숫자를 나열합니다. 2. 2의 배수 삭제: 2는 소수입니다(남김). 2를 제외한 2의 배수(4, 6, 8, 10...)를 모두 지웁니다. 3. 3의 배수 삭제: 다음 남은 숫자인 3은 소수입니다. 3을 제외한 3의 배수(6, 9, 12...)를 모두 지웁니다. (이미 지워진 건 무시) 4. 5의 배수 삭제: 4는 아까 지워졌습니다. 다음 남은 숫자 5는 소수입니다. 5의 배수를 지웁니다. 5. 반복: 이 과정을 구하려는 범위의 제곱근($\sqrt{N}$)까지만 반복하면, 남은 모든 숫자는 소수가 됩니다.
3. 시간 복잡도와 효율성
이 방법의 시간 복잡도는 수학적으로 O(N log(log N))으로 증명되어 있습니다. 이는 거의 O(N), 즉 선형 시간에 가까울 정도로 엄청나게 빠른 속도입니다. 100만이나 1,000만 단위의 큰 범위에서 소수를 대량으로 구해야 할 때, 사실상 유일한 해결책입니다.
4. 구현 코드 (Python 예시)
def sieve_of_eratosthenes(n):
# 처음엔 모두 소수(True)라고 가정 (0, 1은 제외)
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
# 2부터 n의 제곱근까지만 검사
for i in range(2, int(n**0.5) + 1):
if is_prime[i]: # i가 소수라면
# i의 배수들을 모두 소수 아님(False) 처리
for j in range(i * i, n + 1, i):
is_prime[j] = False
return [x for x in range(n + 1) if is_prime[x]]
안쪽 반복문을 `i * 2`가 아닌 `i * i`부터 시작하는 최적화 기법을 사용하면 중복 제거를 더 줄일 수 있습니다.
1. 대량의 소수를 구할 때 하나씩 나누어보는 방식은 너무 느립니다.
2. 에라토스테네스의 체는 소수의 배수들을 지워나가는 방식으로 O(N log log N)의 초고속 성능을 냅니다.
3. 소수 구하기 문제에서 N이 크다면(10만 이상) 무조건 이 알고리즘을 떠올려야 합니다.