『素数』を数えて落ちつくんだ……。“素数の無限性”の証明する「エラトステネスの篩」「ユークリッドの証明」「エルンスト・クンマーの証明」をやさしく解説してみたエラトステネスの篩の素数判定法霊夢： まず、エラトステネスの篩という素数判定法の紹介をする。この方法自体はかなり有名だから、知っている人も多いかもしれない。おまけにエラトステネスは紀元前200年に活躍したエジプト数学者、つまりかなり古い時代に考案されたやり方なんだ。 たとえば2～20までの数字があったとする。この中から素数となるものを見つけ出す。やり方は単純、まず2以外の偶数をすべて消す。次に3以外の3の倍数を全部消す。はい、終わり。 これで残ったやつが素数です。エラトステネスの篩の最強なところは、この圧倒的計算量の少なさである。このためアルゴリズムに使われたりする。さて、このエラトステネスの篩から、こんな疑問が生じる。先程は1から20までで考えていたが、これを無限個の自然数で操作するとき、そして操作が有限回で終わるかどうかというのは、素数が有限個か無限個か？ という問いと同じになる。 実
