エラトステネスの篩（ふるい）を行う際の配列サイズについて

はじめに

下記の自分の記事で配列サイズの見積もりを誤っていた。

JavaScript の場合わりと配列サイズはアバウトでよく，そもそもサイズも型も不定で var a = []; と宣言できてしまうし，var a = new Array(256); のようにサイズを定義して宣言した場合でも，当初宣言したサイズを超えたアクセス，たとえば a[300] に書き込んでも読み込んでもエラーにはならない。ただし，このようなアクセスを行うとパフォーマンスは格段に落ちることが知られている。詳しくは下記の記事を参照されたい。

最大のパフォーマンスを得るには必要な配列のサイズを最初に定義し，この範囲内でアクセスが完結するよう注意しなくてはならない。

自然数をそのまま配列に割り当てる場合

与えられた自然数 $N$ に対して，$N$ の平方根を超えない自然数最大値 $N_1 = [\sqrt{N}]$ までの素数を求める。素数判定を行う自然数 $i$ とすると範囲は $1 \le i \le N_1$ となる。この自然数 $i$ が素数か否かを判定する配列をそのまま a[i] としてアクセスできるようにするためには var a = new Array(N1 + 1); と宣言しなくてはならない。これは JavaScript の配列がゼロオリジンであるため。

エラトステネスの篩（ふるい）では最小の素数 2 からスタートするため a[0] も a[1] も必要ない。このため自然数 $i$ が素数か否かを判定する配列を a[i - 2] としてアクセスするようにすれば配列宣言は var a = new Array(N1 - 1); で済む。ただ，高々２つの要素をケチる代償として，配列のアクセスがほんの少しだけ複雑になってしまう。

逆に配列のアクセスをシンプルにするため，配列の要素を大きめに確保したとも言える。

奇数を配列に割り当てる場合

自然数 $N_1$ 以下の奇数最大値 $N_2$ を

N_2 = \cases{
N_1 & \(N_1\ \bmod 2 \ne 0\) \\
N_1 - 1 & \(N_1\ \bmod 2 = 0\)
}

とおく。整数 $j$ を用いて奇数 $m = 2j + 1$ とおく。奇数 $m$ の範囲 $1 \le m \le N_2$ であり，整数 $j$ の範囲は $0 \le j \le (N_2 - 1) / 2$ となる。奇数 $m = 2j + 1$ が素数かどうかの判定用配列 a[j] を考えると，配列のサイズは $1 + (N_2 - 1) / 2$` となる。

なお，筆者の前回の記事では配列のサイズを $1 + [N_1/2]$ としていたが，これは誤っていた。具体例を挙げると分かり易い。

$N_1$	$N_2$	$1 + [N_1 / 2]$	$1 + (N_2 - 1) / 2$
$100$	$99$	$51$	$\color{red}{50}$
$101$	$101$	$51$	$51$
$102$	$101$	$52$	$\color{red}{51}$
$103$	$103$	$52$	$52$

ということで少し多めに確保していたことが分かる。

連続する８個の奇数をビット毎に割り当てする場合

前回の自分の記事のコメント欄にて，１つの奇数が素数か否かを保持するフラグにわざわざ１バイト使うのは勿体ない。８つの奇数をビット毎にまとめて１バイトで保持できるのではないか？という提案を受けた。こうすると必要な配列のサイズの計算はますます複雑になる。

配列に必要なサイズは表にまとめて整理すると分かり易い。

ここで奇数 $m = 2j+ 1$ を示す $j$ の最大値 $N_3 = (N_2 - 1)/2$ とおく。$1 \le m \le N_2$ かつ $0 \le j \le N_3$ である。

$N_1$	$N_2$	$N_3$	配列のサイズ
$1 \le N_1 \le 16$	$1 \le N_2 \le 15$	$0 \le N_3 \le 7$	$1$
$17 \le N_1 \le 32$	$17 \le N_2 \le 31$	$8 \le N_3 \le 15$	$2$
$33 \le N_1 \le 48$	$33 \le N_2 \le 47$	$16 \le N_3 \le 23$	$3$
$49 \le N_1 \le 64$	$49 \le N_2 \le 63$	$24 \le N_3 \le 31$	$4$

必要なサイズは $1 + [(N_1 - 1) / 16]$ または $1 + [N_2 / 16]$ または $1 + [N_3 / 8]$ となる。

２，３の倍数を除いた自然数を配列に割り当てる場合

自然数 $N_1$ 以下の奇数最大値 $N_2$ を

N_2 = \cases{
N_1 & \(N_1\ \bmod 2 \ne 0\) \\
N_1 - 1 & \(N_1\ \bmod 2 = 0\)
}

とおく。さらに$N_2$ 以下で３の倍数でない奇数最大値 $N_3$ を

N_3 = \cases{
N_2 & \(N_2\ \bmod 3 \ne 0\) \\
N_2 - 2 & \(N_2\ \bmod 3 = 0\)
}

とおく。

２，３の倍数ではない自然数 $m$ を整数 $j, k$ を用いて $m = 6j + 2k - 1$ と表す。$j \ge 1$，$k = \lbrace 0, 1 \rbrace$ である。この $m$ が素数か否かの判定フラグを格納する配列 a[i] とすると，$i = 2j + k$ となる。すなわり $m = 6j + 2k - 1$ は $i =2j + k$ 番目の要素となる。

$j$	$i = 2j + k$		$m = 6j + 2k - 1$
	$k = 0$	$k = 1$	$k = 0$	$k = 1$
$0$	$0$	$1$	$-1$	$1$
$1$	$2$	$3$	$5$	$7$
$2$	$4$	$5$	$11$	$13$
$3$	$6$	$7$	$17$	$19$
$4$	$8$	$9$	$23$	$25$
$5$	$10$	$11$	$29$	$31$
$6$	$12$	$13$	$35$	$37$

配列 a[] のサイズは $N_3$ によって決まる。$N_3 \bmod 3 = 1$ の場合と $N_3 \bmod 3 = 2$ の場合に分けて考える。

• $N_3 \bmod 3 = 1$ の場合 $k = 1$ であり，配列のサイズは $2 + (N_3 - 1) / 3$ となる。
• $N_3 \bmod 3 = 2$ の場合 $k = 0$ であり，配列のサイズは $2 + (N_3 - 2) / 3$ となる。

具体例を挙げると分かり易い。たとえば $N_3 = 35$ のとき，$k = 0$ なので配列のサイズは $2 + (35 - 2)/3 = 13$ 個となる。また $N_3 = 31$ のとき，$k = 1 $ なので配列のサイズは $2 + (31 - 1)/3 = 12$ 個となる。

以上をまとめると配列のサイズは $2 + (N_3 - N_3 \bmod 3) / 3 = 2 + [N_3/3]$ となる。

このような配列 a[] の大きさを前々回の記事では $2 + [N_1 / 3]$ として割り当てていたが，こちらも少し多めに割り当てていたことが分かった。

$N_1$	$N_2$	$N_3$	$2 + [N_1/3]$	$2 + [N_3/3]$
$100$	$99$	$97$	$35$	$\color{red}{34}$
$101$	$101$	$101$	$35$	$35$
$102$	$101$	$101$	$36$	$\color{red}{35}$
$103$	$103$	$103$	$36$	$36$
$104$	$103$	$103$	$36$	$36$
$105$	$105$	$103$	$37$	$\color{red}{36}$
$106$	$105$	$103$	$37$	$\color{red}{36}$
$107$	$107$	$107$	$37$	$37$
$108$	$107$	$107$	$38$	$\color{red}{37}$
$109$	$109$	$109$	$38$	$38$