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

# はじめに

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

https://qiita.com/TETSURO1999/items/a8321c80405a70755c41

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

http://nmi.jp/2019-06-09-The-reason-you-should-avoid-new-array-100

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

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

与えられた自然数 $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$ を

```math
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$` となる。

なお，[筆者の前回の記事](https://qiita.com/TETSURO1999/items/a8321c80405a70755c41)では配列のサイズを $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$|

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

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

[前回の自分の記事のコメント欄](https://qiita.com/TETSURO1999/items/a8321c80405a70755c41#comment-4f47195eb77d6ee16a89)にて，１つの奇数が素数か否かを保持するフラグにわざわざ１バイト使うのは勿体ない。８つの奇数をビット毎にまとめて１バイトで保持できるのではないか？という提案を受けた。こうすると必要な配列のサイズの計算はますます複雑になる。

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

ここで奇数 $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$ を

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

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

```math
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$ 番目の要素となる。

<table>
<thead>
<tr><th rowspan=2 style="text-align:center;">$j$</th>
    <th colspan=2 style="text-align:center;">$i = 2j + k$</th>
    <th colspan=2 style="text-align:center;">$m = 6j + 2k - 1$</th></tr>
<tr><th style="text-align:center;">$k = 0$</th>
    <th style="text-align:center;">$k = 1$</th>
    <th style="text-align:center;">$k = 0$</th>
    <th style="text-align:center;">$k = 1$</th></tr>
</thead>
<tbody>
<tr><td style="text-align:center;">$0$</td>
    <td style="text-align:center;">$0$</td>
    <td style="text-align:center;">$1$</td>
    <td style="text-align:center;">$-1$</td>
    <td style="text-align:center;">$1$</td></tr>
<tr><td style="text-align:center;">$1$</td>
    <td style="text-align:center;">$2$</td>
    <td style="text-align:center;">$3$</td>
    <td style="text-align:center;">$5$</td>
    <td style="text-align:center;">$7$</td></tr>
<tr><td style="text-align:center;">$2$</td>
    <td style="text-align:center;">$4$</td>
    <td style="text-align:center;">$5$</td>
    <td style="text-align:center;">$11$</td>
    <td style="text-align:center;">$13$</td></tr>
<tr><td style="text-align:center;">$3$</td>
    <td style="text-align:center;">$6$</td>
    <td style="text-align:center;">$7$</td>
    <td style="text-align:center;">$17$</td>
    <td style="text-align:center;">$19$</td></tr>
<tr><td style="text-align:center;">$4$</td>
    <td style="text-align:center;">$8$</td>
    <td style="text-align:center;">$9$</td>
    <td style="text-align:center;">$23$</td>
    <td style="text-align:center;">$25$</td></tr>
<tr><td style="text-align:center;">$5$</td>
    <td style="text-align:center;">$10$</td>
    <td style="text-align:center;">$11$</td>
    <td style="text-align:center;">$29$</td>
    <td style="text-align:center;">$31$</td></tr>
<tr><td style="text-align:center;">$6$</td>
    <td style="text-align:center;">$12$</td>
    <td style="text-align:center;">$13$</td>
    <td style="text-align:center;">$35$</td>
    <td style="text-align:center;">$37$</td></tr>
</tbody>
</table>

配列 `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[]` の大きさを[前々回の記事](https://qiita.com/TETSURO1999/items/38ddcc0f4f3411924fe9)では $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$|