素数判定のときに平方根をとってそれ以下の素数で割り切れるか判定しますが
https://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q10229022395
素数、みなさんご存じですよね。１と自分でしか割れない数。
ある数ｎが素数かどうかを調べるには、その数ｎを既知の小さい素数から、つまり２，３，５，７，１１……という数で割ってみて、そのｎまで割り切れなければ素数、という方法で調べると思っていました。
ところが本日、
『ある数nの平方根√nをそれより小さい素数で割ってみて、割れなければ素数』
という判定方法がある事を知りました……、どういうこと？
上記の知恵袋とか色々説明を読みましたが「数学が解る人間しかわからない」説明ばかりで素人にはまるでわからん！ しかしようやく自分で納得する説明にたどりついたので、未来の自分向けに備忘録で書いておきます。
説明
(1)
ある数nが素数ではない（つまり1と自分以外で割り切れる）、とします。
すると「n = a * b」という式で表せます。例「21 = 3 * 7」
(2)
すると「a と b のどちらかは √n 以下」ということになります。
何故？！
↓
理由
もし『 a と b の両方とも √n より大きい』ならば、二つを掛けた「a * b」の答えが「√n * √n = n」より大きいことになってしまい、最初に決めた「n = a * b」と矛盾するからです。
ということは前提が間違っていたので「a と b のどちらかは √n 以下」となります。
(3)
ということで、ある数nの約数 a と b のどちらかは「√n 以下」にあることが確定しました。
ですから、ある数nを素数判定するとき、nまでにある素数で延々割らずとも、「2以上、√n 以下」にある素数で割ってみるだけで良いのです。
例えば √n が「5.xxxxx …」とかなら、n を素数の2, 3, 5 で割ってみるだけでいい。そのどれかがnの約数のはずです。
もしちゃんと約数が見つかればよし。もし約数が見つからなければ「ある数nが素数でない」という前提が間違っていたことになるので、ある数nは素数だと解ります……
ここまでかみ砕いて書いてくれているサイトが無いのは、私がそれだけ飲み込みの悪いアホだからなのだろう……（自嘲）
