MENU
カテゴリー
おすすめプログラミングスクール紹介中! 一覧はこちらから

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

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

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

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

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

ウチダ

数学界では有名な数 $57$ を取り上げてみました(笑)。元ネタについては「【57は素数!?】グロタンディーク素数とは(ただの天才による勘違いです)」の記事をご覧ください。

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

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

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

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

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

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

スポンサーリンク
目次

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

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

それは…

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

これです!

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

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

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

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

【エラトステネスのふるいのやり方】
今回は $1$ ~ $100$ までの素数をすべて見つけてみよう。
1.$1$ ~ $100$ までの数をすべて書き記す。
2.$1$ は素数ではないので、赤線で消す。
3.$2$ に青い $〇$ をつけ、$2$ で割り切れるものすべてを赤線で消す。
4.これを $\sqrt{100}=10$ まで繰り返す。
5.残ったものすべてに青い $〇$ をつける。
6.青い $〇$ が付いたものすべてが素数である。
エラトステネスのふるいのやり方【アニメーションでわかりやすく解説】

※このアニメーションは2秒ごとに移り変わり、計7枚あります。最後のスライドは4秒間静止します。

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

面倒くさいかもしれませんが、これで $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$ 回と、まあ大変です。

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

\begin{align}10000×\log \log 10000&≒10000×\log 9.21\\&≒10000×2.22\\&=22200 \ (回)\end{align}
と、およそ $\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年生で学ぶ知識が必須なので、ここではスルーしますね。[/ふきだし]

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

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

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

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

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

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

以上で終わりです。

よかったらシェアしてね!
  • URLをコピーしました!
  • URLをコピーしました!
スポンサーリンク

コメントを残す

コメント一覧 (1件)

  • ≪…「愚直に割り算する方法」と「エラトステネスのふるい」…≫とは別の
    [陰陽道]の[陰陽]で「素数」を[創生」するのはどうでしょうか・・・

    これは、『幻のマスキングテープ』で[眺望]するある種の『刀狩』ゲームで
    ⦅自然数⦆の[群]を[眺望]しよう。

    『身体がする数学』で[回転運動]と[直進運動]で
    「身についた」・[身につけた」とする
    [人]の文化(文明)としての⦅自然数⦆は、
    [絵本]『もろはのつるぎ」で・・・

コメントする

CAPTCHA


目次