ビット配列による素数表の改良の改良

ビット配列を使ったエラトステネスの篩を改良で書いた内容をさらに発展させて偶数だけを素数表に持たないだけでなく３の倍数、５の倍数も持たないようにすればメモリ使用量をさらに減らせるじゃんと気づいた。

2の倍数と3の倍数を素数表に持たない場合、必要になるメモリは、数値 $N$ までの素数表を作成するとして

$N - N(\frac{1}{2} + \frac{1}{3} - \frac{1}{6}) = \frac{N}{3}$
となり前よりさらに17%程度のメモリが節約できる。ただしこれまで2の倍数かどうかを調べるだけだったインタフェース関数での剰余演算の回数が3の倍数かどうか調べるために1回増える。

2の倍数と3の倍数と、さらに5の倍数も持たない場合、必要になるメモリは

$N - N(\frac{1}{2} + \frac{1}{3} + \frac{1}{5} - \frac{1}{6} - \frac{1}{10} - \frac{1}{15} + \frac{1}{30}) = \frac{4N}{15} = 0.266... \times N$
となり前と比べてさらに23%程度のメモリが節約できる。ただしインタフェース関数での剰余演算が2回増える。

前は1e8までの素数表を得るのに32bit unsigned intを使って $10^8/32/2 = 1562500$ (ビット)で190KB。2と3の倍数を持たないと $10^8/32/3 \approx 1041667$ で127KB。2と3と5の倍数を持たないと $10^8/32 \times \frac{4}{15} \approx 833333$ で101KB。

2,3,5の倍数を消すやり方なら32bit unsigned int全ての素数表を格納するのに必要なメモリは4.2MB。単純にint配列に0,1で保持すると511MB必要になる。