素数判定表・素数リスト

概要

素数判定表を作る．

計算量

$O(n \log \log n)$

使い方

$n$ 以下の整数が判定可能な素数判定表を作る．remove - erase すると素数表になる．

実装

std::vector<int> eratosthenes_sieve(int n) {
    std::vector<int> ps(n + 1);
    std::iota(ps.begin() + 2, ps.end(), 2);
    for (int i = 2; i * i <= n; ++i)
        if (ps[i])
            for (int j = i * i; j <= n; j += i) ps[j] = 0;
    return ps;
}

std::vector<int> make_primes(int n) {
    std::vector<int> ps = eratosthenes_sieve(n);
    ps.erase(std::remove(ps.begin(), ps.end(), 0), ps.end());
    return ps;
}