181が素数であることの確認

ひとつ前の記事の中で、181や199が素数である確認はしてくださいね。
と書きました。

素数とは、『1とその数自身以外に約数をもたない自然数』のことです。ただし、1は素数には含みません。

そんなわけですので、ある数Nが素数であるかどうかは、Nをその数より小さい整数で割っていくことによって調べることができます。
2で割ってどうか、3で割ってどうか、4で割ってどうかと進め、いずれの整数でも割り切れないことが分かれば、ある数Nは素数であると判定できますし、どこかで割り切ることができれば、Nは素数ではないと判定できる、というわけです。
調べ方としては難しくはありません。ただし、Nが大きくなると膨大な回数の割り算が必要になります。それが悩みどころです。

「いや、Nが2で割り切れるかどうかを調べたのなら、4で割り切れるかを調べる必要はないのでは？」という疑問をもたれた方はございますか？
それはナイスアイデアです。
その通り、4で割り切れるくらいなら先に2で割り切れているはずですよね。
そのように考えると、Nを割って確かめるのは、Nより小さい素数で実施すれば良い、ということになります。

では、本稿の主題に近づいていきます。
181が素数であるか、を調べるには、ここまでのアイデアを使うと・・

181÷2
181÷3
181÷5
181÷7
181÷11
181÷13
181÷17
181÷19

と調べ、最後は179で割り切れるかを調べて終わることになります。
「いやいや、ちょっと待ってよ。179は素数なの？」という疑問が出てきますよね。179が素数であると分かるのなら、181が素数なのかも分かりそうなものですから。それに「179まで調べるんじゃあ、調査数はほとんど減らないじゃない！」とも。
これらの疑問はもっともです。
ですが、いったん保留しておきましょう。

お話を戻します。
181÷2
181÷3
181÷5
181÷7
181÷11
181÷13
181÷17
181÷19

と順に調べていくのですが、実は調べるのは、181÷13までで大丈夫なのです。
その理由ですが、

13×13＝169
17×17＝289

169＜181＜289

ですから、181を13で割ったとき、もし割り切れるのであれば商は13より大きな数であることが分かります。
一方181を17で割ったとき、もし割り切れるのであれば商は17よりも小さい数であったことも分かります。つまり、もし181が17で割り切れるのであれば、その商はここまでに発見されているはず、なのです。

13²＜181＜17²

この不等式を見て、181÷13まで確認すればOKなんだ、と判断します。

ということは、この場合、179も同様の理由で素数ですし、この稿の最初に挙げた199も素数だと判定できる、ということになります。
この判定方法を理解すると、素数判定の調査数はずいぶん減らすことができるのです。