エラトステネスの篩のやり方やその計算量とは？【素数を発見しよう】

こんにちは、ウチダです。

いつもお読みいただきましてありがとうございます。

さて、皆さんは「これは素数！」とか「これは合成数！」とか、どうやって判断してますか？

たとえば $57$ だと、$57=3×19$ が成り立つので、もちろん合成数ですね＾＾

実は、素数かどうか判定するには、愚直に割り算をするしかないのですが、その上で少しでも計算量を減らし高速化したものが、「エラトステネスの篩（エラトステネスのふるい）」という方法です。

[ふきだし set=”悩む男性”]エラトステネスの篩？聞いたことないな。どんなやり方なの？[/ふきだし]

[ふきだし set=”悩む女性”]エラトステネスの篩のやり方は知ってるわ。具体的に計算量がどのぐらい減るか詳しく知りたいわ。[/ふきだし]

よって本記事では、こういった悩みを持つ方向けに、「エラトステネスの篩とは何か」そのやり方から、エラトステネスの篩がどのように応用されているかまで

• 東北大学理学部数学科卒業
• 実用数学技能検定１級保持
• 高校教員→塾の教室長の経験あり

の僕がわかりやすく解説します。

エラトステネスの篩とは？【素数の見つけ方】

「愚直に割り算する方法」と「エラトステネスの篩」の一番の違い。

それは…

• 通常の方法　…　自然数 $n$ が素数かどうかを判定する
• エラトステネスの篩　…　自然数 $n$ までの素数を一気に求める。

これです！

[ふきだし set=”ウチダ”]ここが大きく異なるところであり、一番重要な部分です。[/ふきだし]

[ふきだし set=”考える男性”]なるほど！確かにこれで計算量はグッと抑えられそうだね。じゃあ、さっそく具体的なやり方を教えてよ。[/ふきだし]

ということで、エラトステネスの篩のやり方を、アニメーションを用いてわかりやすく解説していきます。

エラトステネスの篩のやり方

以上がエエラトステネスの篩のやり方です。

面倒くさいかもしれませんが、これで $100$ までの素数をすべて見つけることができました♪

[ふきだし set=”ウチダ”]エラトステネスの篩は、よくプログラミングなどに応用される、優秀なアルゴリズムです。プログラムを打ち込むだけで素数を求めることができるので、とても重宝します。[/ふきだし]

補足：なぜ $\sqrt{n}$ までの割り算で良いのか

今回の例の通り $n=100$ として考えてみましょうか。

たとえば $100$ は $5$ で割り切ることができます。

また、$100$ は $20$ でも割り切ることができます。

ここで質問です。

はたして、「 $100$ は $20$ で割り切れる」という情報は必要でしょうか？

$$100=5×20=20×5$$

[ふきだし set=”考える男性”]たしかに、$5$ で割り切れることさえわかれば、$20$ で割り切れることは当たり前だね。[/ふきだし]

つまり、もし $\sqrt{n}$ より大きい数で割り切れたら、その前に $\sqrt{n}$ より小さい数で割り切れてるはずでしょー、というわけです。

スポンサーリンク

エラトステネスの篩の計算量は？【どのぐらい高速か？】

それでは最後に、エラトステネスの篩の計算量はどれくらいか、比較して見てみましょう。

• 通常の方法　…　$n\sqrt{n}$ 回ぐらいの割り算が必要
• エラトステネスの篩　…　$n\log \log n$ 回ぐらいの割り算が必要

たとえば、$n=10000$ としてみましょう。

すると、通常の方法の計算量は、$10000×\sqrt{10000}=10^6$ 回と、まあ大変です。

しかし、一方のエラトステネスの篩の計算量は、

と、およそ $\displaystyle \frac{1}{50}$ に抑えることができます。

では、なぜそうなるのか。

通常の方法での計算量はわかるかと思いますので、エラトステネスの篩にしぼって少し解説します。

エラトステネスの篩の計算量の式

まず、素数 $2$ で割り算する回数は、大体 $\displaystyle \frac{n}{2}$ 回です。

次に、素数 $3$ で割り算する回数も、大体 $\displaystyle \frac{n}{3}$ 回です。

次も大体 $\displaystyle \frac{n}{5}$ 回，その次も大体 $\displaystyle \frac{n}{7}$ 回…。

よってこれらをすべて足し合わせればいいので、$$\frac{n}{2}+\frac{n}{3}+\frac{n}{5}+…=n(\frac{1}{2}+\frac{1}{3}+\frac{1}{5}+…)$$

となり、ようは素数の逆数和に $n$ をかけたものとなります。

ここまで押さえておくと、面白さがより感じられますね。

[ふきだし set=”ウチダ”]素数の逆数和は $∞$ に発散するのですが、その発散のスピードが大体 $\log \log n$ と同じぐらいで、とっても遅いんですね～。これらを理解するためには、高校３年生で学ぶ知識が必須なので、ここではスルーしますね。[/ふきだし]

まとめ：エラトステネスの篩を使って素数を発見しよう！

本記事の要点を $3$ つにまとめます。

1. 自然数 $1$ ～ $n$ までの素数を一気に求めることができる。
2. $\sqrt{n}$ までで割り切れるものを消していけばOK。
3. 全体の計算量は $n\sqrt{n}$ → $n\log \log n$ ぐらいに抑えられる。

$n$ までの素数を一気に見つけることができるから、計算量が抑えられる、ということですね。

素数を見つけるときは、ぜひエラトステネスの篩を使ってみてください＾＾

「整数の性質」全 25 記事をまとめました。こちらから次の記事をCHECK!!

以上で終わりです。