エラトステネスのふるい：古代の知恵が織りなす、素数の神秘への旅
エラトステネスのふるい：古代の知恵が織りなす、素数の神秘への旅 夜空に輝く無数の星々のように、自然数の中には特別な輝きを放つ数が存在します。それが素数です。 古代ギリシアの天文学者、エラトステネスは、この宇宙の神秘を解き明かす鍵となる素数を効率的に見つける方法を考案しました。それが、 エラトステネスのふるい と呼ばれるアルゴリズムです。 ふるいにかけるように、素数を篩い分ける エラトステネスのふるいは、まるで宝石をふるいにかけて純粋な宝石だけを取り出すように、自然数の中から素数だけを抽出する巧妙な仕組みです。 1. 準備 まず、2から調べたい最大の数nまでの自然数を並べます。 各数を素数かどうか判定するためのフラグを用意します。最初は全て「素数である」と仮定します。 2. ふるいにかける 最初に残っている数の中で最小の数を素数として確定します。 確定した素数の倍数を全て「合成数である」とマークします。 まだマークされていない数の中で最小の数を素数として確定し、再び倍数をマークします。 この操作を、全ての数が素数か合成数と確定するまで繰り返します。 3. 素数の収穫 最終的に「素数である」とマークされていた数が、求める素数です。 例：1から10までの素数を見つける 2, 3, 4, 5, 6, 7, 8, 9, 10 の数を並べる。 2は素数なので、2の倍数である4, 6, 8, 10を消す。 残った数の中で最小の3は素数なので、3の倍数である6, 9を消す。 残った数5, 7は素数なので、これ以上消す数は無い。 よって、1から10までの素数は2, 3, 5, 7となる。 エラトステネスのふるいの魅力 シンプルで美しいアルゴリズム: 複雑な計算を必要とせず、誰でも理解できる直感的な方法です。 効率性: 素数を効率的に見つけることができ、大きな数に対しても比較的短い時間で計算できます。 古代からの知恵: 2000年以上前に考案されたアルゴリズムが、現代でもコンピュータサイエンスの分野で活用されていることは驚きであり、ロマンを感じます。 エラトステネスのふるいは、単なる計算方法にとどまらず、古代の人々が自然数に抱いていた神秘に対する探求心と、それを解き明かそうとする知的好奇心の結晶です。 素数の世界は、無限に広がる宇宙のように