에라토스테네스의 체(Sieve of Eratosthenes): 개념, 원리 및 구현

1. 에라토스테네스의 체란?

에라토스테네스의 체(Sieve of Eratosthenes)는 고대 그리스의 수학자 에라토스테네스가 만든 소수(prime number)를 구하는 고전적인 알고리즘이다. 1부터 N까지의 자연수 중에서 소수만을 빠르고 효율적으로 찾을 수 있는 방법으로, 오늘날에도 널리 활용된다.

특히 많은 수의 소수를 한꺼번에 찾아야 할 때 효율적인 알고리즘으로, 단순하면서도 시간 복잡도가 낮아 알고리즘 입문자나 대회 준비자에게도 필수적인 기법이다.

2. 동작 원리

에라토스테네스의 체는 다음과 같은 방식으로 동작한다.

1. 2부터 N까지의 모든 정수를 나열한다.
2. 2는 소수이므로 남겨두고, 2의 배수는 모두 제거한다.
3. 남은 수 중 다음 수(3)를 선택하고, 그 수의 배수들을 모두 제거한다.
4. 이를 반복하여 N의 제곱근까지 진행하면, 남은 수들은 모두 소수이다.

이 과정은 불필요한 연산을 줄이고, 반복되는 배수 제거를 통해 빠르게 소수를 추려낼 수 있도록 해준다.

3. 예제

예를 들어, N = 30일 때

• 초기 리스트: [2, 3, 4, 5, 6, ..., 30]
• 2의 배수 제거: [2, 3, 5, 7, 9, 11, ...]
• 3의 배수 제거: [2, 3, 5, 7, 11, 13, ...]
• 5의 배수 제거: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

최종 결과: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 (소수)

4. 구현 (Java)

import java.util.*;

public class Sieve {
    public static List<Integer> sieve(int n) {
        boolean[] isPrime = new boolean[n + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;

        for (int i = 2; i * i <= n; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= n; j += i) {
                    isPrime[j] = false;
                }
            }
        }

        List<Integer> primes = new ArrayList<>();
        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) primes.add(i);
        }

        return primes;
    }

    public static void main(String[] args) {
        int n = 100;
        List<Integer> primes = sieve(n);
        System.out.println("소수 목록 (2~" + n + "): " + primes);
    }
}

5. 시간 및 공간 복잡도

구분	복잡도
시간 복잡도	O(N log log N)
공간 복잡도	O(N)

 

매우 빠른 성능으로, 일반적으로 10⁷ 이하 범위의 소수를 구하는 데 적합하다.

6. 활용 사례

• 소수 판별 및 나열
• 수학 문제 해결 (골드바흐의 추측, 쌍둥이 소수 등)
• 암호학 (RSA 알고리즘의 소수 생성 등)
• 경우의 수 계산 (소수 개수 기반 조합 문제)
• 프로그래밍 대회 및 알고리즘 문제 풀이

7. 결론

에라토스테네스의 체는 단순하지만 강력한 소수 구하기 알고리즘으로, 정수론과 수학적 알고리즘의 기초이자 핵심 도구이다. 특히 제한된 범위 내에서 다수의 소수를 빠르게 구해야 할 때 가장 우선적으로 고려되는 방법이며, 다양한 분야에서 실용적으로 활용되고 있다.