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

はじめに

前記事

szarny.hatenablog.com

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

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

  • 何故,素数判定の際に,その数の平方根までに約数を持つかどうかを調べるだけで済むのか
  • 何故,合成数 xp \leq \sqrt{x} を満たす素因子 p をもつと言えるのか
  • 何故,エラトステネスの篩のアルゴリズム素数を篩い分けることができるのか

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

エラトステネスの篩

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

  1. 指定整数  \displaystyle N までの整数を列挙する. (つまり,1, 2, ..., N)
  2. \displaystyle 1 は,素数ではなく単数なので除去する.
  3. 残った整数の中で最小のものを素数(ここでは \displaystyle p )とする.整数が残っていないならば終了
  4. \displaystyle p の倍数は素数ではないので,\displaystyle ( p, N ] \displaystyle p の倍数を除去する.
  5. 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}]にも必ず約数を持つ.

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

終わりに

短く済ますつもりでしたが,いろんなことを考えながら書いているとダラダラ長くなってしましました.
もし,不適切な点や論理が飛躍している点などがありましたら,教えて頂けると幸いです.

参考文献

数学ガールの秘密ノート 整数で遊ぼう

note2.hyuki.net