エラトステネスの篩の空間効率
「常識的」が「普通」に書き換わったのはなぜだろう．
それはちょうどこのへんを読んだので、その通りかも、と思って修正した結果です。
さて、それはともかくとして、エラトステネスの篩は空間効率が悪いのか。さてどうだろう。
例では、5 * 10^7 までの素数表を作ったが、この範囲には素数が 3,001,134 個ある。これを全て 4Bytes の整数で記憶すると必要メモリは大体12MB くらい。
対して、エラトステネスの篩で使う表は1つの数あたり1bitあれば十分で、しかも偶数の素数は2だけなので、2だけ特別扱いして偶数用の領域を省けば、5 * 10^7 / 2 / 8 = 3,125,000 Bytes。
ということで、範囲が 10^7 程度のオーダで、List<Integer> に変換しないようにすれば、実はエラトステネスの篩のほうが効率が良い。
