エラトステネスのふるい法は、指定された数より小さいすべての素数を見つけるために使用される数学的アルゴリズムです。このシステムは、2,000 年以上前にギリシャの数学者エラトステネスによって開発されました。
素数とは、1 とそれ自体の 2 つの約数のみを持つ 1 より大きい自然数です。たとえば、数値 2 は、1 と 2 でしか割り切れないため、素数になります。一方、数値 4 は、1、2、4 で割り切れるため、素数ではありません。
一般に、エラトステネスのふるい法は、指定された数より小さいすべての素数を見つける効率的な方法です。これを行うには、数値のリストが使用され、見つかった素数の倍数すべてに取り消し線が引かれます。プロセスの最後に、取り消し線が引かれていない数字が素数になります。
エラトステネスのふるいはどのように機能しますか?
エラトステネスのふるいは、多くの素数を比較的迅速かつ簡単に見つけるために使用できる強力な概念です。これは、素数の倍数は素数になることができないという単純な原理に基づいて機能します。たとえば、3 は素数であるため、6、9、12、15 およびその他すべての 3 の倍数は素数になることはできません。
指定された 2 つの整数間の素数を特定しようとしたり、新しい素数を検索しようとすると、検索が開始される前にすべての素数の倍数が更新される可能性があります。
エラトステネスのふるいはフィルターのように機能し、数値のリストから以前のすべての素数の倍数を削除して、テストに時間を無駄にしないようにします。
この方法をよりよく理解するには、実際の例を使用する必要があります。次のように20 未満のすべての素数を見つける方法を以下で見てみましょう。
- 2 から 20 までの数字のリストを書きます: 2、3、4、5、6、7、8、9、10、11、12、13、14、15、16、17、18、19、20。
- 2 の倍数をすべて削除します: 2、3、5、7、9、11、13、15、17、19。
- 3 の倍数をすべて消去します: 2、3、5、7、11、13、17、19。
- 5 の倍数 (2、3、5、7、11、13、17、19) はすべて無視します。
- 7 の倍数をすべて取り消します: 2、3、5、7、11、13、17、19。
交差していない数字は素数です: 2、3、5、7、11、13、17、19。
エラトステネスのふるいを使って素数を見つける実践例
素数を見つける他の方法と比較して、エラトステネスのふるいは素早く簡単に使用できます。特にコンピューターが利用できない場合はそうです。このプロセスには、除算、乗算、検索要素は必要ありません。
どちらの場合も、ふるいは明らかに素数ではない数値をすぐに排除します。この方法の概念は、あらゆる数値を因数に分割できるという事実に基づいています。これらの因数は、必要に応じて、素因数だけが残るまで分割できます。
これを数値の素因数分解といいます。このようなプロセスは、すべての非素数が固有の素因数のセットを持っていることを示します。
言い換えれば、素数以外の数はその因数として素数を持ちます。素数が特定されると、その倍数はすべて自動的に非素数とみなされます。エラトステネスのふるいはそれらを排除する方法です。例として、1 から 30 までの素数を考えてみましょう。
まず理解する必要があるのは、素数とは、数字の 1 とそれ自体で割られる数字であるということです。これは明らかなので、エラトステネスのふるいの例を見てみましょう。
- 1から30までの数字を表に書きます。
| 1 | 2 | 3 | 4 | 5 |
| 6 | 7 | 8 | 9 | 十 |
| 十一 | 12 | 13 | 14 | 15 |
| 16 | 17 | 18 | 19 | 二十 |
| 21 | 22 | 23 | 24 | 25 |
| 26 | 27 | 28 | 29 | 30 |
- 次に、数値 2 を素数としてマークし、リストから 2 の倍数をすべて削除します。
| 1 | 2 | 3 | 4 | 5 |
| 6 | 7 | 8 | 9 | 十 |
| 十一 | 12 | 13 | 14 | 15 |
| 16 | 17 | 18 | 19 | 二十 |
| 21 | 22 | 23 | 24 | 25 |
| 26 | 27 | 28 | 29 | 30 |
- 次に、次のマークのない数字である 3 を素数とみなし、リストからその倍数をすべて取り消します。
| 1 | 2 | 3 | 4 | 5 |
| 6 | 7 | 8 | 9 | 十 |
| 十一 | 12 | 13 | 14 | 15 |
| 16 | 17 | 18 | 19 | 二十 |
| 21 | 22 | 23 | 24 | 25 |
| 26 | 27 | 28 | 29 | 30 |
- 次に、5 にマークを付けずに、5 の倍数をすべてリストから削除します。この場合は単純で、5 と 0 で終わる数字を削除するだけです。
| 1 | 2 | 3 | 4 | 5 |
| 6 | 7 | 8 | 9 | 十 |
| 十一 | 12 | 13 | 14 | 15 |
| 16 | 17 | 18 | 19 | 二十 |
| 21 | 22 | 23 | 24 | 25 |
| 26 | 27 | 28 | 29 | 30 |
- 最後に、次のステップは、2 と 3 の倍数 (14 と 21) を取り消して、すでに削除された 7 の倍数を見つけることです。
このプロセスの後、2 から 30 までの素数は 2、3、5、7、11、13、17、19、23、29 であることがわかります。
エラトステネスのふるいは日常生活にどのような応用があるのでしょうか?
このアルゴリズムは日常生活ではあまり実用的ではないように思えるかもしれませんが、実際にはいくつかの重要な用途があります。
エラトステネスのふるいの最も一般的な用途の 1 つは暗号化です。素数は、多くの暗号化システムのセキュリティにおいて基本的な役割を果たします。したがって、エラトステネスのふるいは、素数を見つけて生成するための便利なツールです。
エラトステネスのふるいのもう 1 つの関連した応用は、数値の因数分解です。大きな数の因数を見つけたい場合は、エラトステネスのふるいを使用して、どの素数がその数を割るかを決定できます。これは、数学の問題を解決したり、数値の構造を分析したりする場合に役立ちます。
さらに、エラトステネスのふるいは、最適化アルゴリズムやデータセットの研究にも使用されます。たとえば、大規模なデジタル データ セット内のパターンや傾向を見つけるために使用できます。
一般に、エラトステネスのふるいは非常に単純な数学的アルゴリズムですが、日常生活において多くの実用的な用途があります。
エラトステネスのふるいを子供にどう説明する？
これは複雑なテーマのように思えるかもしれませんが、例やゲームを使って子供たちに簡単に説明できます。エラトステネスのふるいを子供たちに説明するためのアイデアをいくつか紹介します。
- 素数とは何かを説明することから始めます
- 素数を見つけるためにエラトステネスのふるいがどのように使用されるかを子供たちが理解できるようにします。これを行う 1 つの方法は、エリミネーション ゲームを使用することです。たとえば、2 から 30 までの数字のリストから 2 の倍数をすべて削除するように子供たちに指示します。その後、3 の倍数をすべて削除する、というようになります。消去されなかった数字は素数です。
- この概念を子供たちにとってより興味深いものにするために、さまざまな状況で素数を見つける遊びをすることができます。たとえば、友達の生年月日や住んでいる家の番号から素数を探すことができます。
この概念を強化するには、子供たちがさまざまな数値範囲でエラトステネスのふるいを使用して素数を見つける練習をする価値があります。これらのアクティビティを通じて、子供たちはエラトステネスのふるいを楽しく発見し、数学や日常生活におけるそのふるいの重要性を理解することができます。
エラトステネスのふるい法の歴史
エラトステネスは、紀元前 3 世紀に生きたギリシャの数学者および天文学者です。実際、彼はエラトステネスのふるい法など、数学と科学への重要な貢献で知られています。
この偉大な人物は、豊かな実験と知的好奇心の時代に生きました。このヘレニズム時代には、ギリシャの科学と哲学が西洋世界全体に広がりました。
世界中から学者や科学者が新しい図書館や学校に集まり、議論し、議論し、互いに学び合いました。エラトステネスは、これらのアイデアの多くを多数の数学的発見の基礎として使用しました。これらの発見の 1 つはエラトステネスのふるいでした。
エラトステネスは、当時最も重要な研究教育機関の 1 つであるアレクサンドリア図書館の司書でした。エラトステネスは、図書館司書として働いている間に、エラトステネスのふるい法を開発しました。この方法は、特定の数より小さい素数を見つける必要がある場合に最適な方法の 1 つです。
エラトステネスのふるい手順は、それ以来数学の基本ツールとして使用されています。このため、暗号化から数学研究まで幅広い分野に応用できます。素数を見つけるためのより高速な方法はありますが、エラトステネスのふるい法は依然として効果的で広く使用されている方法です。