エラトステネスの“ふるい”

エラトステネス

　古くから知られている方法としては、エラトステネスの“ふるい”というのがあります。 　エラトステネス(紀元前276頃～紀元前194頃)は古代ギリシャの天文学者です。 　その方法は2以上の整数を並べ、2を残して一つ置きに数を消し、次に残った最初の3を残し、二つ置きに数を消し、次に残った最初の5を残して4つ置きに消していきます。素数でもって、次々と消去を実行して残った数が素数です。 　恐ろしく悠長な方法に見えますが、素数を探す一般的方法としては効率はよいのです。 　この方法では、N以下の自然数に対しては√N以下の素数で試せば十分です。つまり、100以下であれば、√100 = 10以下の素数2, 3, 5, 7で試せば十分なのです。実際、実行していただくと、100以内の素数が25個見つかります。 　それはなぜかといいますと、N以下の自然数nが合成数でn=pqと書けたとします。 　いま、1＜p≦q＜nとします。このとき、p2≦pq=n≦Np2≦pq=n≦N なので、p≦√Nとなります。もしpが素数であればそれは√Nより小さい。 　もしpが合成数であれば、ある素数rで割れることになり、nは素数rで割り切れるので、素数rはやはり√Nより小さい。こうして、√N以下の素数で試せばよいことになります。 　歴史的には代数式で素数を作り出すことが試みられてきましたが、そうは問屋が卸さないようです。R. クーラント＆H. ロビンズ著『数学とは何か』(岩波書店、1966)には次のような例があります。 　0≦n≦40 ならば、代数式(n2 － n + 41)は素数になります。また、0≦n≦79 ならば、代数式(n2－79n+1601)は素数になります。 　一般には、与えられた数が素数であるか否かを判定するのは難しいのです。 　しかし、皮肉にも現代ではそのこと自体がとても大切な性質として重宝されています。 　今日はカード時代となり、カードの情報を保護する方法がとても重要になっています。そして、その秘密が漏れないようにするためには暗号が必要になります。その暗号法に素数が大活躍しているのです(暗号については、拙著『学びなおし！　 数学 代数・解析編』で、1節を割き詳しくご説明しています)。 　現代は、誰も予測できなかった数学の時代といえるでしょう。 ---------- 学びなおし！　 数学 代数・解析編　なっとくする数学キーワード29 ロングセラー『なっとくする数学記号』の著者にして、数学教育を知り尽くした専門家だから書けた、「学びなおし」の決定版！　 ----------