はじめに
前記事
にて,Pythonで素数判定を行う各種のアルゴリズムを実装し,その実行効率を比較しました.
しかし,その中でどうしても疑問に思ったことが3点ありました.
- 何故,素数判定の際に,その数の平方根までに約数を持つかどうかを調べるだけで済むのか
- 何故,合成数
は
を満たす素因子
をもつと言えるのか
- 何故,エラトステネスの篩のアルゴリズムで素数を篩い分けることができるのか
今回は,エラトステネスの篩を実際に手作業で行い,それらの疑問へのヒントを得たいと思います.
実験
ことはじめ
今回は, として行います.
まずは,列挙して単数を除去します.
2について
すると,最小の整数2が得られました.
2は素数ですね.ついでに,2の倍数を除去していきます.
3について
次に,最小の整数3が得られました.
3は素数でしょうか?
3が素数ではないと仮定すると,3はの範囲に約数を持っていなければなりません.
ここで,その範囲に当てはまるのは2だけです.
しかし,先ほど2の倍数はすべて除去したはずです.
よって,除去されていない3は2の倍数ではない,つまり2を約数に持たないため素数であると言えるでしょう.
3を素数とし,3の倍数を除去していきます.
7について
次は,7が得られます.
しつこいようですが,7を素数とし,7の倍数を除去していきます.
11について
次に,11が得られます.
11を素数とし,11の倍数を除去していき...と思いましたが,11の倍数はすべて除去されてしまっています.
振り返りと一般化
過程を振り返る
振り返って考えてみましょう.
最初に2を素数とした時,除去されているものは1を除いて存在しませんでした.
つまり,ここでは2自身を除く,100以下の全ての「2の倍数」が除去対象となります.
次に3を素数とした時,除去されているものは1と「2の倍数」です.
つまり,ここでは3自身と「2の倍数」を除く,100以下の全ての「3の倍数」が除去対象となります
そして,5を素数とした時,除去されているものは1と「2の倍数」と「3の倍数」です.
つまり,ここでは5自身と「2の倍数」と「3の倍数」を除く,100以下の全ての「5の倍数」が除去対象となります.
このあたりでパターンが見えてきます.
パターンの発見
前項のパターンを一般化しましょう.
つまり,以下のように言えるのではないか,ということです.
を素数とした時,除去されているものは1と「2の倍数」と「3の倍数」と ... と「(
の手前の素数)の倍数」である.
つまり,ここでは自身と「2の倍数」と「3の倍数」と ... と「(
の手前の素数)の倍数」を除く,100以下の全ての「
の倍数」が除去対象となる
これは,例を考えてみれば至極当然のことです.
例えば,2を素数とした時,は除去されます.そのため,3を素数とした時,
を除去するか考える必要はありません.
掛け算の順序を入れ替えただけで,すでに除去済みであることは明らかだからです.
ここから,こんなことも言えそうです.
を素数とした時の除去対象を
と表すとき,
必ずである.
結び付けて考える
先ほどの一般化と,11以降で除去作業が必要なくなったことを組み合わせて考えてみます.
先ほどの一般化した予測が正しいなら,以下のことが言えます.
11を素数とした時,
自身と「2の倍数」と「3の倍数」と「5の倍数」と「7の倍数」を除く,100以下の全ての「11の倍数」が除去対象となる
そのような除去対象は存在するのでしょうか?
考え得る最初の除去対象は,でしょう.
しかし,この数は明らかに100を超えているので除去対象ではありません.
ゆえに,11を素数とした時,最初の除去対象が100より向こう側にあるため,除去作業は必要なくなったということができるでしょう.
11以降の数に対しても,同じことが言えます.
そして平方根へ
では,除去作業が不必要になるのは,どのタイミングなのでしょうか?
先ほどの一般化より, を素数とした時,除去対象は
から始まります.
先に示した通り,に関しては,考える必要はありません.
これまでの考えより,「除去作業が不必要になる」ということは「除去作業の最初の対象が範囲から飛び出ている」ということだと考えられます.
そして,その「除去作業の最初の対象」とは, を素数とした時
です.
つまり,が上限である
を超えている場合,除去作業は不必要だということができます.
また,除去作業が不必要になった最初の素数以降でまだ除去されていないものは,今後除去対象になることはありません.
よって,無条件に素数であると判定して構わないということです.
まとめ
まとめます.
エラトステネスの篩において,素数判定の上限を
とする時,除去作業が行われるのは
が成り立つ
を素数とした時のみである.
つまり,の範囲に含まれる合成数は,
の範囲に含まれる素数を「素数とした」時に,必ず除去対象となっている.
言い換えると,の範囲に含まれる合成数は,
の範囲に含まれる素数の内,どれかの倍数になっている.
よって, 整数が合成数であるとき,
に約数を持つなら,
にも必ず約数を持つ.
以上より,素数判定の際に,その数の平方根までに約数を持つかどうかを調べるだけで済むと言える
終わりに
短く済ますつもりでしたが,いろんなことを考えながら書いているとダラダラ長くなってしましました.
もし,不適切な点や論理が飛躍している点などがありましたら,教えて頂けると幸いです.