エラトステネスの篩 - peria.jpエラトステネスの篩 x 以下の素数を列挙する方法として，また， プログラムの基礎として有名なエラトステネスの篩 (the sieve of Eratosthenes) を紹介します． プログラムとして単純なところから， エラトステネスの篩としての最高速付近までの考え方， 作り方を紹介します． 目次 エラトステネスの篩の実装 2 乗数の応用 自明な合成数の除去 高速メモリの効率的利用 その他高速化処理 ループ展開，配列変数の不使用 最後でない項目が「その他」というのは違和感があるが， 「その他」に含まれる項目の1つ1つがさほど大きな話題ではないこと， また，最後のループ展開等は 1 度その最適化を行うと， その他の高速化手段を考案した際に組み込みにくくなること， の 2 つの理由から順番をこのようにしている． プログラム時間計測 プログラム実行時間については， 素数自体を出力する部分を実行し
