エラトステネスの篩の活用法を総特集！ 〜 高速素因数分解・メビウスの反転公式 〜 #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
    }

• 計算量: $n/2 + n/3 + n/5 + n/7 + n/11 + \ldots = O(n \log \log n)$
  • cf: 計算量が調和級数になるループ

高速素因数分解・高速約数列挙

• 通常、素因数分解や約数列挙は $O(\sqrt{n})$ の計算量がかかる。エラトステネスの篩による前計算をすることで、素因数分解が $O(\log n)$ で計算可能になる。

• 高速素因数分解・高速約数分解の前計算として、エラトステネスの篩の要領で最小因子を求める

  • 例えば $63 = 3 \times 3 \times 7$ の最小因子は $3$
  • 素因数分解は最小因子で割り続ければいいだけの話になって計算量が $\log n$ になる

• 素数判定・素因数分解・約数列挙の計算量は以下の通り（$\sigma(n)$ は $n$ の約数の数)

  	通常	エラトステネスの篩
  素数判定	$O(\sqrt{n})$	$O(1)$
  素因数分解	$O(\sqrt{n})$	$O(\log n)$
  約数列挙	$O(\sqrt{n})$	$O(\sigma (n))$

  $O(n \log \log n)$ の前処理計算をすることで、1回あたりの各種クエリが早く計算できる。

メビウス関数

• 普通に計算すると O(√n) (素因数分解と同じ)
• エラトステネスの篩をすると、O(1)

高速ゼータ変換

• 指数の部分に関する多次元累積和

難しかったので一旦スキップ

区間篩