2015/01/28

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

分野: 整数問題  レベル: マニアック

エラトステネスのふるい:$n$ 以下の素数を全て見つけ出す高速な方法。

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

愚直な方法

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

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

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

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

エラトステネスのふるい

エラトステネスのふるい
1:$2$ から $n$ までの整数を並べる。
2:生き残っている数の中で一番小さい(かつまだ $p$ として使われていない)ものを新たに $p$ とおき,$p$ 以外の $p$ の倍数を全て消していく。
3:2の操作を繰り返していき,$p$ が $\sqrt{n}$ を越えたら終了。最終的に生き残ったものが素数。

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

・生き残っている素数候補の集合を $A$ とおく。
$A=\{2,3\cdots, 30\}$

・ $p=2$ の倍数をふるい落とす
$A=\{2,3,5,7,9,11,13,15,17,19,21,23,25,27,29\}$

・ $p=3$ の倍数をふるい落とす
$A=\{2,3,5,7,11,13,17,19,23,25,29\}$

・ $p=5$ の倍数をふるい落とす
$A=\{2,3,5,7,11,13,17,19,23,29\}$

・次は $p=7$ となるが $\sqrt{30}$ より大きいので終了。 $30$ 以下の素数が高速に求まった!

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

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

エラトステネスのふるいによる計算量を考えてみます。ここで言う計算量とは $n$ が大きいとき,アルゴリズムの遂行に必要な基本演算(四則演算など)の回数を大雑把に評価したものです。

(定数倍くらいの違いなどは無視して)大雑把に $f(n)$ であるような量を $O(f(n))$ と書きます。

(計算量の導出)
$2$ でふるいおとすのに $\tfrac{n}{2}$ 回,$3$ でふるい落とすのに $\tfrac{n}{3}$ 回,$5$ でふるい落とすのに $\tfrac{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: 素数にまつわる覚えておくべき性質まとめ

分野: 整数問題  レベル: マニアック