エラトステネスのふるいとその計算量

更新 2021/03/07

エラトステネスの篩（ふるい）とは， $n$ 以下の素数を全て見つけ出す高速な方法です。

エラトステネスのふるいの概要と，愚直に計算するよりも速いこと（計算量が $O(n\log\log n)$ であること）を紹介します。

愚直な方法

エラトステネスのふるいの前に，まずは愚直な方法で $n$ 以下の素数を全て列挙することを考えてみます。

愚直な方法

$1$ から $n$ まで順々に素数かどうか判定する。
$k$ が素数かどうかは $\sqrt{k}$ 以下の素数たちで割り算すればよい。

$\sqrt{k}$ が登場したのは $k$ が合成数なら必ず $\sqrt{k}$ より小さい素因数を持つからです。

例えば $31$ が素数かどうか判定するときに $5 <\sqrt{31} <6$ なので $5$ 以下の素数で割り切れないことを証明すればOKです。つまり「 $2$ の倍数でない， $3$ の倍数でない， $5$ の倍数でない」ことを確認すればOKです。

エラトステネスのふるい

$2$ から $n$ までの整数を並べる。
生き残っている数の中で一番小さい（かつまだ $p$ として使われていない）ものを新たに $p$ とおき， $p$ 以外の $p$ の倍数を全て消していく。
2の操作を繰り返していき， $p$ が $\sqrt{n}$ を越えたら終了。最終的に生き残ったものが素数。

$n=30$ で実験してみます。

n=30の場合の例

$2$ から $30$ までの整数を並べる。
$p=2$ の倍数をふるい落とす
$p=3$ の倍数をふるい落とす
$p=5$ の倍数をふるい落とす
次は $p=7$ となるが $\sqrt{30}$ より大きいので終了。 $30$ 以下の素数は，ここまで生き残った $2,3,5,7,11,13,17,19,23,29$ である！

合成数は $p$ として選ばれる前にふるい落とされるので， $p$ として選ばれるのは素数のみです。つまり「 $\sqrt{n}$ 以下の素数」回だけ上記のふるい落とす操作を行うことになります。

エラトステネスのふるいの計算量

エラトステネスのふるいによる計算量を考えてみます。ただし，ここで言う計算量とは $n$ が大きいとき，アルゴリズムの遂行に必要な基本演算（四則演算など）の回数を大雑把に評価したものです。定数倍くらいの違いなどは無視して）大雑把に $f(n)$ であるような量を $O(f(n))$ と書きます。→オーダー記法（ランダウの記号）の定義と大雑把な意味

計算量の導出

以下のように実装した場合を考える。

要素数 $n$ ですべての要素が $1$ である配列 $A$ を用意しておく
$A$ のすべての $2$ の倍数番目の要素に $0$ を代入する
$A$ のすべての $3$ の倍数番目の要素に $0$ を代入する
$A$ のすべての $5$ の倍数番目の要素に $0$ を代入する
$\sqrt{n}$ 以下の素数まで続ける
最後に $A$ の各要素を見て $1$ であるのが何番目かを列挙する

手順1と手順6の計算量は $O(n)$ である。残りの手順については， $2$ でふるいおとすのに $\dfrac{n}{2}$ 回， $3$ でふるい落とすのに $\dfrac{n}{3}$ 回， $5$ でふるい落とすのに $\dfrac{n}{5}$ 回， $\cdots$ の定数時間の演算（配列への代入）を行うので計算量は，

$\displaystyle\sum_{p <\sqrt{n}}\dfrac{n}{p}=\dfrac{n}{2}+\dfrac{n}{3}+\dfrac{n}{5}+\cdots$

（ただし，和は $\sqrt{n}$ 以下の素数全体に関して取る）

ここで $n$ が十分大きいとき $\sqrt{n}$ までの素数の逆数和はだいたい $\log\log \sqrt{n}=\log\log n+\log \dfrac{1}{2}$ くらい（→素数の逆数和が発散することの証明）なので，計算量は $O(n\log\log n)$ となる。

愚直な方法による計算量との比較

最初に紹介した愚直な方法による計算量も求めてみます。

計算量の導出

$k$ が素数かどうかを判定するのに最大 $\sqrt{k}$ 回くらいの割り算が必要なので，全体の計算量はおおよそ $\displaystyle\sum_{k=1}^n\sqrt{k}$

これは $n$ が大きいとだいたい $\displaystyle\int_0^n\sqrt{x}dx=\dfrac{2}{3}n\sqrt{n}$

よって，計算量は $O(n\sqrt{n})$

$O(n\log\log n)$ と $O(n\sqrt{n})$ とでは $n$ が大きいとき圧倒的に前者の方が計算量が少なくなります（対数関数でさえ増加が遅いのだから $\log\log n$ はもっと遅い！）。エラトステネスのふるいの素晴らしさがなんとなく分かっていただけたかと思います。

なお，素数定理とかを使えば愚直な方法に対してもう少し計算量を厳しく評価できますが，それでもエラトステネスのふるいの方が速いです。

素数の逆数和が出てくるのは楽しいですね。

Tag:素数にまつわる覚えておくべき性質まとめ

この記事の監修者

マスオ

高校数学の美しい物語の管理人。「わかりやすいこと」と「ごまかさないこと」の両立を意識している。著書に『高校数学の美しい物語』『超ディープな算数の教科書』。記事の誤植やわかりにくい等のご指摘はお気軽にメールください！