Sieve

クラス · 素数列挙・判定

template <int N = (1 << 22)>
struct Sieve;

概要

素数の篩

0 <= x < N の範囲は前計算した篩で高速に答える。範囲外は上記の free function （Miller-Rabin, Pollard’s rho）にフォールバックするため、Sieve はどんな大きさの入力に対しても常に正しい答えを返す（範囲外を assert で弾いていた旧実装とは異なる）。素数判定・列挙はエラトステネスの篩（mod30 wheel + セグメント化）で行う。 mod30 の wheel とビットマスクで 1 バイトに 8 個の数を詰め、篩い込みは L1 キャッシュに収まるセグメント単位で行い（segmented sieve）、内側ループは 8 ステップ（wheel 1 周）を展開する。

計算量

構築は $O(N \log\log N)$、範囲内の素数判定は $O(1)$

構築・破棄

名前	説明	計算量
`(constructor)`	N未満の素数判定表を構築する	$O(N\log\log N)$

メンバ関数

名前	説明	計算量
`is_prime`	素数判定（範囲外は Miller-Rabin にフォールバックするので任意の x で正しい）	$x<N$ なら $O(1)$、それ以外は $O(\log x)$ 回のmod乗算
`prime_numbers`	x 以下の素数を昇順に列挙	$O(x)$
`prime_factorization`	素因数分解	初回の範囲内呼出しは $O(N)$、以後は $O(\log x)$。範囲外は期待 $O(x^{1/4} \log x)$

メンバの詳細

prime_numbers

std::vector<int> prime_numbers(int x) const;

x 以下の素数を昇順に列挙

パラメータ x: x < N
計算量: $O(x)$

prime_factorization

std::vector<std::pair<std::uint64_t, int>> prime_factorization(std::uint64_t x);

素因数分解

x < N なら最小素因数テーブル（初回呼び出し時に $O(N)$ で遅延構築）で $O(\log x)$、x >= N なら Pollard’s rho にフォールバックする

戻り値: (素数, 指数) のペアを素数の昇順で列挙したもの
計算量: 初回の範囲内呼出しは $O(N)$、以後は $O(\log x)$。範囲外は期待 $O(x^{1/4} \log x)$