MENU

エラトステネスのふるいとは?【素数の求め方(見つけ方)で最適な方法です】

2019 12/15
エラトステネスのふるいとは?【素数の求め方(見つけ方)で最適な方法です】

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

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

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

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

ウチダのアイコン画像ウチダ

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

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

悩む男性のアイコン画像悩む男性
エラトステネスのふるい?聞いたことないな。どんなやり方なの?
悩む女性のアイコン画像悩む女性
エラトステネスのふるいのやり方は知ってるわ。具体的に計算量がどのぐらい減るか詳しく知りたいわ。

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

  • 東北大学理学部数学科卒業
  • 教員採用試験に1発合格 → 高校教諭経験アリ

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

スポンサーリンク
目次

エラトステネスのふるいとは?【素数の求め方(見つけ方)はこれで完璧!】

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

それは…

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

これです!

ウチダのアイコン画像ウチダ
ここが大きく異なるところであり、一番重要な部分です。
考える男性のアイコン画像考える男性
なるほど!確かにこれで計算量はグッと抑えられそうだね。じゃあ、さっそく具体的なやり方を教えてよ。

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

エラトステネスのふるいのやり方

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

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

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

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

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

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

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

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

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

ここで質問です。

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

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

考える男性のアイコン画像考える男性
たしかに、$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$ をかけたものとなります。

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

ウチダのアイコン画像ウチダ
素数の逆数和は $∞$ に発散するのですが、その発散のスピードが大体 $\log \log n$ と同じぐらいで、とっても遅いんですね~。これらを理解するためには、高校3年生で学ぶ知識が必須なので、ここではスルーしますね。

エラトステネスのふるいに関するまとめ

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

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

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

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

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

あわせて読みたい
整数の性質とは?【高校数学Aの解説記事総まとめ25選】
整数の性質とは?【高校数学Aの解説記事総まとめ25選】「整数の性質」の総まとめ記事です。本記事では、整数の性質の解説記事全25個をまとめています。「整数の性質をしっかりマスターしたい」「整数の性質を自分のものにしたい」という方は必見です。

以上で終わりです。

【小中高生向け】オンライン家庭教師とは?(オススメ5選をご紹介)
【大学生向け】専門書は高いのに売れない?そんなことないです(専門書買取おすすめ4選)

コメント

コメント一覧 (1件)

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

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

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

コメントする

目次
閉じる