ブックタイトルROOT No.19

概要

ROOT No.19

さて，この方法だと，たとえば47が素数かどうかを調べるためには，2,3,5,7,11,13,17,19,23,29,31,37,41,43についてチェックする必要があります。これはかなり大変な作業です。しかし，実際のところ，ある自然数xが素数であるかどうかを調べるためには，までの素数をチェックするだけで済みます。≒6.86ですから，2,3,5までのチェックで十分です。47の場合，2,3,5のどれでも割り切れませんから，素数だと判断できます。エふるいラトステネスの篩ふるい「篩」という道具は，曲物枠の底に格子状の網を張ったもので，砂と石を選り分けたりするときに使います。中学生だって小さい頃砂場で遊んだ経験があると思うのですが，名称まではあまり知らないようです。この篩を自然数に使います。たくさんの自然数をがばっと篩に入れて振ると，素数だけが選り分けられる―そんなイメージのアルゴリズムが「エラトステネスの篩」です。とてもシンプルな作業ですが，原理としては現在でもよく使われています（もちろんコンピュータの力を借りることになります）。この篩を考案したとされるエラトステネス（BC275～194）は，今からおよそ2200年前のエジプトで活躍したギリシャ人の学者です。同時期に活躍したアルキメデス（BC287～212）は，彼の友人です。エラトステネスは数学だけでなく，天文学，地理学においても大きな業績を残しています。特に「地球の大きさを測った人物」として有名です。ご案内「星田直彦」名義での城田先生の近著『図解よくわかる測り方の事典』（角川新書）もぜひご覧ください。算数・数学情報誌ROOT vol.19 7