エラトステネスの篩の活用法を総特集！ 〜 高速素因数分解・メビウスの反転公式 〜 #AtCoder - Qiita
pub fn sieve_of_eratosthenes(n: usize) -> Vec<bool> {
let mut is_prime = vec![true; n + 1];
is_prime[0] = false;
is_prime[1] = false;
for p in 2..=n.sqrt() {
if !is_prime[p] {
continue;
}
for q in (p * 2..=n).step_by(p) {// n/p 回ループ
is_prime[q] = false;
}
}
is_prime
}
$63 = 3 \times 3 \times 7$ の最小素因数は $3$、素因数の数は $2$
DP で bool 値 DP、数え上げDP、最小化 DP があるようにエラトステネスの篩 (bool) の最小化バージョンや最小化バージョンもある。
通常、素因数分解や約数列挙は $O(\sqrt{n})$ の計算量がかかる。エラトステネスの篩による前計算をすることで、素因数分解が $O(\log n)$ で計算可能になる。
高速素因数分解・高速約数分解の前計算として、エラトステネスの篩の要領で最小因子を求める
素数判定・素因数分解・約数列挙の計算量は以下の通り（$d(n)$ は $n$ の約数の数)
| 通常 | エラトステネスの篩 | |
|---|---|---|
| 素数判定 | $O(\sqrt{n})$ | $O(1)$ |
| 素因数分解 | $O(\sqrt{n})$ | $O(\log n)$ |
| 約数列挙 | $O(\sqrt{n})$ | $O(d(n))$ |
$O(n \log \log n)$ の前処理計算をすることで、1回あたりの各種クエリが早く計算できる。