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

🧠 에라토스테네스의 체 (Sieve of Eratosthenes) 간단 정리
에라토스테네스의 체는 N 이하의 모든 소수를 빠르게 구하는 대표적인 알고리즘이다.
소수가 아닌 수(합성수)를 지워나가는 방식으로 작동하며, 시간 복잡도가 매우 효율적이다.

✅ 핵심 아이디어

• 2부터 N까지 모든 수를 소수라고 가정한다.

• 현재 수의 배수들을 모두 제거한다.

• 남은 수들은 전부 소수다!

🔧 구현 핵심 코드 (Java)

boolean[] isPrime = new boolean[N + 1];
Arrays.fill(isPrime, true);

isPrime[0] = false;
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;
        }
    }
}

📌 설명
isPrime[i] == true → i는 소수

i * i <= N까지만 검사해도 충분

j = i * i부터 시작 → 이미 지워진 수 중복 제거

🧾 요약
항목 설명
시간 복잡도 O(N log log N)
공간 복잡도 O(N) (boolean 배열)
활용 예시 소수 판별, 범위 내 소수 구하기, 백준 1929번 등