2023-11-01 エラトステネスの篩 エラトステネスの篩とは ある整数nが与えられた時、このn以下の素数を高速に列挙する方法である。計算量としてはO(n log log n)である。素数判定の方法をn回繰り返すとo(n √n)となる。これに対してエラトステネスはすごい速い。 エラトステネスの篩によって得られる恩恵 1以上n以下の各整数の高速素因数分解 1以上n以下の各整数の高速約数列挙 1以上n以下の各整数のメビウス関数の値を高速に求めること 1以上n以下の各整数のオイラー関数の値を高速に求めること 高速ゼータ変換 高速メビウス変換 添字 GCD 畳み込み qiita.com 上の記事の関数を必要になり次第、実装していきたいな。
