エラトステネスの篩

N以下の素数を高速に列挙するアルゴリズム。

素数の倍数を順に除外し、最後まで残った数を素数とする。

特徴

項目	内容
用途	素数判定・素数列挙
計算量	O(N log log N)
空間計算量	O(N)
前処理後の素数判定	O(1)

考え方

1. 2以上の整数をすべて素数候補とする。
2. 小さい素数から順に、その倍数を除外する。
3. 最後まで残った整数が素数。

pの倍数を除外するときは、p*p から開始すればよい。

p*p より小さいpの倍数は、それ以前の小さい素因数を持つため、すでに除外されている。

また、√Nまで調べれば十分。

実装

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;

    vector<bool> is_prime(n + 1, true);
    is_prime[0] = false;
    if (n >= 1) is_prime[1] = false;

    for (int p = 2; 1LL * p * p <= n; p++) {
        if (!is_prime[p]) continue;
        for (int x = p * p; x <= n; x += p) is_prime[x] = false;
    }

    vector<int> primes;
    for (int i = 2; i <= n; i++)
        if (is_prime[i]) primes.push_back(i);

    for (int p : primes) cout << p << ' ';
    cout << '\n';
}

使用例

入力

30

出力

2 3 5 7 11 13 17 19 23 29

素数判定

前処理後、O(1)で判定できる。

if (is_prime[x]) {
    // xは素数
}

素数列挙

vector<int> primes;
for (int i = 2; i <= n; i++) {
    if (is_prime[i]) primes.push_back(i);
}

注意点

• 0と1は素数ではない。
• 判定できるのは前処理したN以下の整数。
• p*p から倍数の除外を開始すればよい。
• p*p <= N の判定は、整数オーバーフローに注意する。
• 多数の整数について素数判定する場合に有効。
• 非常に大きい整数1つの素数判定には、別のアルゴリズムを検討する。

関連

• 素数判定
• 素因数分解
• SPF（最小素因数）
• 区間篩