エラトステネスの篩

エラトステネスの篩とは

ある整数nが与えられた時、このn以下の素数を高速に列挙する方法である。計算量としてはO(n log log n)である。素数判定の方法をn回繰り返すとo(n √n)となる。これに対してエラトステネスはすごい速い。

エラトステネスの篩によって得られる恩恵

  1. 1以上n以下の各整数の高速素因数分解
  2. 1以上n以下の各整数の高速約数列挙
  3. 1以上n以下の各整数のメビウス関数の値を高速に求めること
  4. 1以上n以下の各整数のオイラー関数の値を高速に求めること
  5. 高速ゼータ変換
  6. 高速メビウス変換
  7. 添字 GCD 畳み込み

qiita.com

上の記事の関数を必要になり次第、実装していきたいな。

素因数分解

素因数分解とは

nを素因酢分解するアルゴリズムは、1 ~ √nに対してaとするとnをaで割れるときにaで割れるだけ割れば良い。この時aが素数でなければaを分解せねばならないが、aは必ず素数である。 最後に残った数は素因数となっているので追加する。ここで1になる可能性があることにも注意せねばならぬ。

実装

必要になったら書きます

応用

約数の個数

素因数分解をn = p1e1p2e2...prerとする。この時、約数の個数は

(e1 + 1)(e2 + 1)(e3 + 1)...(er + 1)となる。

約数の総和

素因数分解をn = p1e1p2e2...prerとする。この時、約数の総和は

(p10 + p11 + ... + p1e1)(p20 + p21 + ... + p2e2)...(pr0 + pr1 + ... + prer)となる。

オイラー関数

ある整数nが与えられる。この整数に対して互いに素なn未満の整数の個数を φ(n)とかく。これをオイラー関数という。 素因数分解をn = p1e1p2e2...prerとする。

φ(n) = n (1 - 1/p1)(1 - 1/p2)...(1 - 1/pr)となる。

約数列挙

約数列挙とは

nの約数を考える。これは、素数判定と同様に1 ~ √nの間でのみ判定して、割り切れた整数をaとすると、それと同時にn / aを答えに追加すれば良い。 ここで注意点だが、a = n / aの時に両方を追加してはならない。

実装

// また実装する必要がある時に関数を作ります。

素数判定法

素数判定とは

与えられた整数nが素数かそうでないかを判定するアルゴリズムである。 普通に考えると、2 ~ n-1 でnが割り切れないかを確認すれば良い。しかし、 n = abとすると、min(a, b)は√nを超えない。これより2 ~ √nの間でのみ割り切れないかを考えると十分であり、これはO(√n)の計算量で実行できる。

実装

fn is_prime(n: usize) -> bool {
    for i in 2..(n + 1) {
        if i.pow(2) > n {
            break;
        }
        if n % i == 0 {
            return false;
        }
    }
    return true;
}

多分こんな感じ。確認もしてないです。実際に使ったりしたらその時に書き直したやつをコピペします。

いもす法

いもす法とは

累積和の応用であり、ある区間に一定値を足す操作を複数回高速でするアルゴリズムである。

実装

let mut imos = vec![0; 2 * 10usize.pow(5) + 2];
for &(s, t, p) in &stp {
    imos[s] += p as isize;
    imos[t] -= p as isize;
}

let mut need = vec![];
for &i in &imos {
    need.push(need.last().unwrap_or(&0) + i);
}

色々と1次元以外にも応用が効くらしいです。

累積和（1次元）

累積和とは

Σ(i = n) ^ m のクエリを高速に解くためのアルゴリズムである。 事前にΣ(i = 0) ^ m を求めておいて、これをS_mとするとS_m - S_(n - 1)が求めたい総和になる。

事前に求めるパートがO(N)であり、それ以降はO(1)でクエリをこなすことができる。

実装

let mut s = [0];
for &a in &a {
    s.push(s.last().unwrap() + a);
}

これはs[i]で[0, i)の総和を求めることができる。実装の問題でこうしているだけでunwrap_or(0)を用いることで[0, i]ともできる。自分はclosed setの方が直感的で好きです。半開区間はLebesgue積分を思い出すなあ。