에라토스테네스의 체 — 소수 판별

JayJi·2026년 4월 4일

알고리즘

목록 보기

10/30

문제	난이도	핵심
1929번 — 소수 구하기	실버 III	기본 구현
2960번 — 에라토스테네스의 체	브론즈 I	K번째 지워지는 수
6588번 — 골드바흐의 추측	실버 I	소수 목록 활용

1. 개념

N 이하의 모든 소수를 찾는 알고리즘이다. 핵심 아이디어는 단 하나다.

소수의 배수는 소수가 아니다.

2부터 시작해서 소수를 발견할 때마다 그 배수를 전부 제거한다. 남은 수가 모두 소수다.

2. 동작 과정

N = 16 기준

단계	기준수 p	p²	제거 대상	이유
1	2	4	4, 6, 8, 10, 12, 14, 16	2의 배수
2	3	9	9, 15	3의 배수 (6, 12는 이미 제거됨)
3	4	16	skip	4는 합성수 (2가 이미 처리)
4	5	25	루프 종료	5² = 25 > 16

최종 소수: 2, 3, 5, 7, 11, 13

3. 핵심 포인트 2가지

바깥 루프가 p * p <= N 인 이유

√N 이상의 수의 배수는 더 작은 소수가 이미 처리했기 때문이다.

p = 5일 때, 5×2=10 → 2가 처리, 5×3=15 → 3이 처리
√N보다 큰 수는 할 일이 없다.

안쪽 루프가 p * p 부터인 이유

p² 미만의 배수는 더 작은 소수가 이미 제거했기 때문이다.

p = 5일 때, 5×2, 5×3, 5×4는 각각 2, 3, 2가 처리
새로 처리할 것은 5×5 = 25부터다.

4. 코드

boolean[] isComposite = new boolean[N + 1]; // 합성수면 true

for (int p = 2; p * p <= N; p++) {          // p를 2부터 √N까지
    if (!isComposite[p]) {                   // p가 소수라면
        for (int m = p * p; m <= N; m += p) { // p²부터 p씩 건너뛰며
            isComposite[m] = true;            // 배수를 합성수로 표시
        }
    }
}

// isComposite[i] == false 인 i (2 이상) 가 소수

5. 1929번 적용 코드 (M 이상 N 이하 소수 출력)

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        boolean[] isComposite = new boolean[N + 1];

        for (int p = 2; p * p <= N; p++) {
            if (!isComposite[p]) {
                for (int m = p * p; m <= N; m += p) {
                    isComposite[m] = true;
                }
            }
        }

        for (int i = M; i <= N; i++) {
            if (i >= 2 && !isComposite[i]) {  // 2 이상이면서 합성수가 아닌 것
                sb.append(i).append("\n");
            }
        }

        System.out.print(sb);
    }
}