알고리즘MathPrimesOptimization

에라토스테네스의 체

범위 내 모든 소수를 O(N log log N)에 찾는 고대 알고리즘

시각화 로드 중...

알고리즘 복잡도

최선O(N log log N)
평균O(N log log N)
최악O(N log log N)
공간O(N)

개요

Algorithm Overview

에라토스테네스의 체(Sieve of Eratosthenes)는 특정 상한 범위 $N$ 이하의 모든 소수(Prime Numbers)를 고속으로 판별해내는 대표적인 정수론 알고리즘입니다.

01

에라토스테네스의 체 핵심 원리

2부터 시작하여 현재 탐색 중인 수가 지워지지 않았다면 소수로 확정하고, 그 수의 모든 배수(합성수)를 체로 치듯이 걸러내어 지워 나갑니다.

  • 배열 초기화: 2부터 $N$까지의 모든 정수를 소수 후보(true)로 설정한 불리언 배열을 준비합니다.
  • 소수 확정 및 배수 소거: 첫 번째 소수 2를 확정하고, $2^2=4$부터 2의 배수($4, 6, 8, dots$)를 모두 합성수(false)로 지웁니다.
  • 다음 미소거 정수 탐색: 지워지지 않고 남아있는 다음 수 3을 소수로 확정하고, $3^2=9$부터 3의 배수($9, 12, 15, dots$)를 지웁니다.
02

$sqrt{N}$ 최적화의 수학적 증명

상한 $N$ 이하의 임의의 합성수 $m$은 $sqrt{m}$ 이하의 소인수를 하나 이상 포함한다는 성질을 활용합니다.

  • 조기 종료 조건: 바깥쪽 루프를 $sqrt{N}$까지만 순회하면 $N$ 이하의 모든 합성수가 완전히 소거됩니다.
  • 중복 소거 방지 ($p^2$ 시작): 소수 $p$의 배수를 지울 때 $p imes 2, p imes 3, dots$ 등 $p^2$ 미만의 배수들은 이미 앞선 더 작은 소수(2, 3)들에 의해 지워졌으므로, 항상 $p^2$부터 시작하여 불필요한 중복 연산을 제거합니다.
  • 시간 복잡도: 소수의 역수 합 공식(Mertens' Theorem)에 의해 $O(N log log N)$이라는 거의 선형에 수렴하는 극상의 속도를 달성합니다.

실행 예제로 확인하기

상한 20에서는 2의 제곱인 4부터 2의 배수를, 3의 제곱인 9부터 3의 배수를 지웁니다. 4는 이미 지워졌으므로 건너뛰며, 5는 √20보다 커서 새 배수 소거가 필요 없습니다. 남는 소수는 2, 3, 5, 7, 11, 13, 17, 19입니다.

학습 목표

  • 배수 소거를 p²부터 시작하는 이유를 설명할 수 있다.

자주 하는 오해

  • 현재 소수 p의 p²보다 작은 배수는 이미 더 작은 소수의 단계에서 지워졌으므로 반복해서 지울 필요가 없습니다.

핵심 정리

  • 체의 바깥 반복은 √N까지만 수행해도 N 이하 모든 합성수를 제거할 수 있습니다.

학습 확인

문제 1

상한 20에서 소수 3의 단계에서 처음 지우는 수는?

핵심 단계

  1. 1

    2부터 N까지 배열 초기화 (모두 "소수 후보")

  2. 2

    p = 2: 소수 확정 → p²(=4)부터 p 간격으로 합성수 표시

  3. 3

    p = 3: 소수 확정 → 9, 12, 15... 합성수 표시

  4. 4

    p = 4: 이미 합성수 → 건너뜀

  5. 5

    √N 이하 모든 p 처리 완료 → 남은 미표시 수 전부 소수 확정

핵심 개념 및 실무 적용 분야

✓작은 범위의 소수를 미리 구해 소인수분해와 소수 판별을 보조하는 전처리
✓코딩 테스트 소수 판별 최적화
✓정수론 연구 및 수학적 패턴 분석
✓해시 테이블의 버킷 크기 결정 (소수 사용)

참고 자료

개념과 기술 규격을 추가로 확인할 수 있는 외부 자료입니다. 시각화는 교육 목적에 맞게 일부 절차를 단순화할 수 있습니다.