에라토스테네스의 체 (Sieve of Eratosthenes)

정의

1부터 N까지의 소수를 빠르게 구하는 대표 알고리즘입니다.

“소수인지 하나씩 판별한다”가 아니라, 소수의 배수를 한 번에 지워서 합성수를 표시하는 방식으로 동작합니다.

핵심 아이디어: “남아 있는 수 = 소수”, “지워진 수 = 합성수”

예) N=30이면 2의 배수(4,6,8..), 3의 배수(9,12,15..)를 지워가며 소수만 남깁니다.

핵심 메시지

단일 숫자 판별은 O(√n)이지만, “구간(1..N) 전체 소수”가 필요하면 체가 정답입니다. 여러 번 소수 판별이 필요한 문제에서 특히 강력합니다.

수학 개념

왜 “배수 지우기”가 소수를 남기는가

합성수는 반드시 “어떤 소수의 배수”다

합성수 n은 n=a×b로 표현되며, a 또는 b는 소인수(소수)를 포함합니다. 따라서 합성수는 반드시 어떤 소수 p의 배수입니다. 체는 이 성질을 그대로 사용합니다.

왜 i×i부터 지워도 되는가

어떤 수 i의 배수 중에서 i×2, i×3, ..., i×(i-1)은 이미 더 작은 수(2,3,...,i-1) 단계에서 지워졌습니다. 그래서 체 구현은 보통 j=i×i부터 시작해 중복 작업을 줄입니다.

중복 제거 포인트: j = i*i부터 마킹

 

알고리즘 개념

동작 과정: “남은 수를 소수로 확정하고 배수 지우기”

단계형 요약

1

isPrime 배열 준비

처음엔 2..N을 “소수 후보(true)”로 두고 시작(0,1은 false)

2

i를 2부터 √N까지 순회

i가 아직 true(소수 후보)면, i는 소수로 확정

3

i의 배수를 지운다

j=i×i부터 N까지 i씩 증가하며 isPrime[j]=false

이 과정을 끝내면, isPrime 배열에서 true로 남아 있는 인덱스가 소수입니다.

복잡도 감각

체는 대략 O(N log log N)로 알려져 있고, 메모리는 O(N)을 사용합니다. N이 커질수록 “√n 판별을 N번 반복”하는 방식보다 훨씬 유리합니다.

 

구현

Java로 구현하기 (실전형 템플릿)

TIP

(1) j는 i*i부터 시작 (중복 제거)
(2) 반복 조건은 i*i <= N 형태로 (sqrt 호출 생략)
(3) N이 매우 크면 boolean[] 메모리(O(N))를 고려

import java.util.*;

public class SieveEratosthenes {

    // isPrime[i] == true  => i는 소수
    static boolean[] sieve(int n) {
        boolean[] isPrime = new boolean[n + 1];
        if (n < 2) return isPrime;

        Arrays.fill(isPrime, true);
        isPrime[0] = false;
        isPrime[1] = false;

        for (int i = 2; i * i <= n; i++) {
            if (isPrime[i]) { // i가 소수면
                for (int j = i * i; j <= n; j += i) {
                    isPrime[j] = false; // i의 배수는 합성수
                }
            }
        }
        return isPrime;
    }

    public static void main(String[] args) {
        int N = 30;
        boolean[] isPrime = sieve(N);

        List<Integer> primes = new ArrayList<>();
        for (int i = 2; i <= N; i++) {
            if (isPrime[i]) primes.add(i);
        }
        System.out.println(primes); // [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
    }
}

 

코테 포인트

자주 틀리는 지점(실수 방지)

1

0과 1 처리

0, 1은 소수가 아닙니다. isPrime[0]=false, isPrime[1]=false를 꼭 설정하세요.

2

j 시작점

j를 i*2로 시작하면 중복이 많아집니다. 보통 i*i부터 시작합니다.

3

반복 조건

i는 √N까지만 돌면 충분합니다. i*i <= N 형태가 자주 쓰입니다.

 

요약

체크리스트로 마무리

CHECK

✅ 목적: 1..N 소수를 한 번에 구한다

✅ 아이디어: 소수의 배수를 지워 합성수를 표시한다

✅ 최적화: i는 √N까지만, j는 i*i부터

✅ 복잡도: 대략 O(N log log N), 메모리 O(N)