エラトステネスの篩で調べる素数判定の上限と平方根の関係性

はじめに
エラトステネスの篩
実験
振り返りと一般化
まとめ
終わりに
参考文献
- 数学ガールの秘密ノート整数で遊ぼう

はじめに

前記事

szarny.hatenablog.com

にて，Pythonで素数判定を行う各種のアルゴリズムを実装し，その実行効率を比較しました．

しかし，その中でどうしても疑問に思ったことが3点ありました．

何故，素数判定の際に，その数の平方根までに約数を持つかどうかを調べるだけで済むのか

何故，合成数 $x$ は $p \leq \sqrt{x}$ を満たす素因子 $p$ をもつと言えるのか

何故，エラトステネスの篩のアルゴリズムで素数を篩い分けることができるのか

今回は，エラトステネスの篩を実際に手作業で行い，それらの疑問へのヒントを得たいと思います．

エラトステネスの篩

繰り返しになりますが，エラトステネスの篩とは，以下の手順によって指定整数以下の素数を篩い分けるアルゴリズムです．(実験のため，わざと冗長にしてあります．)

指定整数 $\displaystyle N$ までの整数を列挙する． (つまり， $1, 2, ..., N$ )
$\displaystyle 1$ は，素数ではなく単数なので除去する．
残った整数の中で最小のものを素数(ここでは $\displaystyle p$ )とする．整数が残っていないならば終了
$\displaystyle p$ の倍数は素数ではないので， $\displaystyle ( p, N ]$ の $\displaystyle p$ の倍数を除去する．
3. に戻る

実験

ことはじめ

今回は， $\displaystyle N = 100$ として行います．

まずは，列挙して単数を除去します．
f:id:Szarny:20170927221742p:plain

2について

すると，最小の整数2が得られました．
2は素数ですね．ついでに，2の倍数を除去していきます．
f:id:Szarny:20170927222009p:plain

3について

次に，最小の整数3が得られました．
3は素数でしょうか？
3が素数ではないと仮定すると，3は $\displaystyle (1,3)$ の範囲に約数を持っていなければなりません．
ここで，その範囲に当てはまるのは2だけです．
しかし，先ほど2の倍数はすべて除去したはずです．
よって，除去されていない3は2の倍数ではない，つまり2を約数に持たないため素数であると言えるでしょう．
3を素数とし，3の倍数を除去していきます．
f:id:Szarny:20170927222529p:plain

5について

次は，5が得られます．
5が素数であることは，先ほどと同じようにして証明可能なので，ここでは省略します．
5を素数とし，5の倍数を除去していきます．
f:id:Szarny:20170927222755p:plain

7について

次は，7が得られます．
しつこいようですが，7を素数とし，7の倍数を除去していきます．
f:id:Szarny:20170927223113p:plain

11について

次に，11が得られます．
11を素数とし，11の倍数を除去していき...と思いましたが，11の倍数はすべて除去されてしまっています．
f:id:Szarny:20170927223617p:plain

13以降

これ以降， $13, 17, 19, ..., 97$ と素数が得られますが，それまであった除去作業は一切発生しなくなります．

f:id:Szarny:20170927223944p:plain

一体何故，11以降は除去作業が不必要になったのでしょうか？

振り返りと一般化

過程を振り返る

振り返って考えてみましょう．

最初に2を素数とした時，除去されているものは1を除いて存在しませんでした．
つまり，ここでは2自身を除く，100以下の全ての「2の倍数」が除去対象となります．

次に3を素数とした時，除去されているものは1と「2の倍数」です．
つまり，ここでは3自身と「2の倍数」を除く，100以下の全ての「3の倍数」が除去対象となります

そして，5を素数とした時，除去されているものは1と「2の倍数」と「3の倍数」です．
つまり，ここでは5自身と「2の倍数」と「3の倍数」を除く，100以下の全ての「5の倍数」が除去対象となります．

このあたりでパターンが見えてきます．

パターンの発見

前項のパターンを一般化しましょう．
つまり，以下のように言えるのではないか，ということです．

$p$ を素数とした時，除去されているものは1と「2の倍数」と「3の倍数」と ... と「( $p$ の手前の素数)の倍数」である．
つまり，ここでは $p$ 自身と「2の倍数」と「3の倍数」と ... と「( $p$ の手前の素数)の倍数」を除く，100以下の全ての「 $p$ の倍数」が除去対象となる

これは，例を考えてみれば至極当然のことです．
例えば，2を素数とした時， $2 \cdot 3$ は除去されます．そのため，3を素数とした時， $3 \cdot 2$ を除去するか考える必要はありません．
掛け算の順序を入れ替えただけで，すでに除去済みであることは明らかだからです．

ここから，こんなことも言えそうです．

$p$ を素数とした時の除去対象を $\displaystyle p \cdot \alpha$ と表すとき，
必ず $\displaystyle p \leq \alpha$ である．

結び付けて考える

先ほどの一般化と，11以降で除去作業が必要なくなったことを組み合わせて考えてみます．
先ほどの一般化した予測が正しいなら，以下のことが言えます．

11を素数とした時， $p$ 自身と「2の倍数」と「3の倍数」と「5の倍数」と「7の倍数」を除く，100以下の全ての「11の倍数」が除去対象となる

そのような除去対象は存在するのでしょうか？
考え得る最初の除去対象は， $11 \cdot 11$ でしょう．
しかし，この数は明らかに100を超えているので除去対象ではありません．
ゆえに，11を素数とした時，最初の除去対象が100より向こう側にあるため，除去作業は必要なくなったということができるでしょう．

11以降の数に対しても，同じことが言えます．

そして平方根へ

では，除去作業が不必要になるのは，どのタイミングなのでしょうか？

先ほどの一般化より， $p$ を素数とした時，除去対象は $p \cdot p$ から始まります．
先に示した通り， $p \cdot 1, p \cdot 2, ..., p \cdot p-1$ に関しては，考える必要はありません．

これまでの考えより，「除去作業が不必要になる」ということは「除去作業の最初の対象が範囲から飛び出ている」ということだと考えられます．
そして，その「除去作業の最初の対象」とは， $p$ を素数とした時 $p \cdot p$ です．

つまり， $p \cdot p$ が上限である $N$ を超えている場合，除去作業は不必要だということができます．

また，除去作業が不必要になった最初の素数以降でまだ除去されていないものは，今後除去対象になることはありません．
よって，無条件に素数であると判定して構わないということです．

まとめ

まとめます．

エラトステネスの篩において，素数判定の上限を $N$ とする時，除去作業が行われるのは $p \cdot p \leq N$ が成り立つ $p$ を素数とした時のみである．

$\displaystyle p \cdot p \leq N \Leftrightarrow p \leq \sqrt{N}$

つまり， $[ \lfloor\sqrt{N}\rfloor +1, N]$ の範囲に含まれる合成数は， $[2, \lfloor\sqrt{N}\rfloor ]$ の範囲に含まれる素数を「素数とした」時に，必ず除去対象となっている．
言い換えると， $[ \lfloor\sqrt{N}\rfloor +1, N]$ の範囲に含まれる合成数は， $[2, \lfloor\sqrt{N}\rfloor ]$ の範囲に含まれる素数の内，どれかの倍数になっている．

よって，整数 $x$ が合成数であるとき， $[\sqrt{x}+1, x]$ に約数を持つなら， $[2, \sqrt{x}]$ にも必ず約数を持つ．

以上より，素数判定の際に，その数の平方根までに約数を持つかどうかを調べるだけで済むと言える