에라토스테네스의 체 · 알고리즘 노트

개념

일정 범위 안의 소수를 여러 개 구할 때 사용합니다. 처음에는 $2$ 이상의 수를 모두 소수 후보로 두고, 작은 소수부터 그 배수를 지웁니다.

배수 제거

$2$ 의 배수, $3$ 의 배수, $5$ 의 배수 순서로 표시합니다. 이미 지워진 수는 합성수이므로 그 수의 배수를 다시 순회할 필요가 없습니다.

소수 $p$ 의 배수 표시는 $p^2$ 부터 시작합니다. 그보다 작은 배수 $2p,3p,\dots,(p-1)p$ 는 더 작은 소인수의 배수를 지우는 과정에서 처리됩니다. $p^2>N$ 이 되면 남아 있는 수들이 소수입니다.

$20$ 이하의 소수는 $2,3,5,7,11,13,17,19$ 입니다.

$20$ 까지 구하는 과정을 보면 $2$ 의 배수인 $4,6,8,\ldots,20$ 을 먼저 지웁니다. 다음으로 남아 있는 $3$ 을 선택하고 $9,12,15,18$ 을 지웁니다. $3\times2=6$ 은 $2$ 의 배수로 이미 지웠으므로 $3^2=9$ 부터 시작해도 됩니다. 다음 소수 $5$ 는 $5^2>20$ 이므로 여기서 끝납니다. 합성수라면 제곱근 이하의 소인수가 있어야 하므로, 남은 수 중 아직 지우지 못한 합성수는 없습니다.

이렇게 만든 표는 범위 안의 각 수가 소수인지 바로 확인할 수 있습니다. 질의가 많을수록 같은 수를 반복해서 나누어보는 계산을 줄일 수 있으며, 대신 범위 전체를 저장할 공간이 필요합니다.

복잡도

소수를 구할 범위의 최댓값을 $N$ 이라고 합니다.

연산	시간복잡도	공간복잡도
체 전처리	$O(N\log\log N)$	판별 표 $O(N)$
전처리 후 소수 여부 조회	$O(1)$	추가 $O(1)$

예제

문제

주어진 수 이하의 모든 소수를 구하여라.

입력

첫째 줄에 양의 정수 $N$ 이 주어진다. $2\le N\le9\,999$ 이다.

출력

소수를 오름차순으로 한 줄에 공백을 사이에 두고 출력한다.

예제 코드

C++20

#include <iostream>
#include <algorithm>

using namespace std;

bool prime[10000];

int main() {
    int n, i, j;

    cin >> n;
    fill(prime, prime + n + 1, true);
    prime[0] = false;
    prime[1] = false;
    for (i = 2; i * i <= n; ++i) {
        if (prime[i]) {
            for (j = i * i; j <= n; j += i) {
                prime[j] = false;
            }
        }
    }

    for (i = 2; i <= n; ++i) {
        if (prime[i]) cout << i << ' ';
    }
    cout << '\n';
}

Java 17

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in;
        int n, i, j;
        boolean[] prime;

        in = new Scanner(System.in);
        n = in.nextInt();
        prime = new boolean[n + 1];
        Arrays.fill(prime, true);
        prime[0] = false;
        prime[1] = false;
        for (i = 2; i * i <= n; ++i) {
            if (prime[i]) {
                for (j = i * i; j <= n; j += i) {
                    prime[j] = false;
                }
            }
        }

        for (i = 2; i <= n; ++i) {
            if (prime[i]) System.out.print(i + " ");
        }
        System.out.println();
    }
}

Python 3

n = int(input())
prime = [True] * (n + 1)
prime[0] = prime[1] = False
i = 2

while i * i <= n:
    if prime[i]:
        for j in range(i * i, n + 1, i):
            prime[j] = False
    i += 1

print(*[i for i in range(2, n + 1) if prime[i]])

2.2.3 Sieve of Eratosthenes

개념

배수 제거

복잡도

예제

문제

입력

출력

예제 입력

예제 출력

예제 코드