素数判定の「試し割」のコードについて

Question

前提・実現したいこと

試し割のコードでの分からない点を知りたいです。
あるサイトから実際に試し割ができるコードを参考にさせてもらって、勉強しています。そのため、コードは合っていると思いますが、そのコードで分からない点があります。

発生している問題・エラーメッセージ

エラーメッセージ

該当のソースコード

def is_prime_trial_division(n):
    if n < 2:
        return False
    else:
        for i in range(2, n):
            if i * i > n:
                break
            elif n % i == 0:
                return False
        return True

試したこと

if n < 2:で1を省いていることと、elseのfor文で素数判定したいnを2からnまで繰り返していることは分かったのですが、if文でのii > n:の箇所で何をしたいのかが、よく分かりません。
また、例えばn=7の場合、i=2のとき、22>7ではないので、elifに行き、7/2の余りは0ではないため、return Trueに行くのでしょうか？

補足情報（FW/ツールのバージョンなど）

Answer 1

i*i > n:の条件は、割り算の回数を減らすためのものです。nが合成数の場合、√n以下の数が必ず素因数にあります（√nより大きい数を2つかければnを超えますので、片方が√n以下でないとかけてnになりません）。

例えばn=7の場合、i=2のとき、2*2>7ではないので、elifに行き7/2の余りは0ではないため

次の3に進みますが、3*3=9と7を超えるため、ループから抜けてTrueを返します。

Comments

[bbettbn]

ありがとうございました！
とてもわかりやすかったです！

Answer 2

素数判定では、iがsqrt(n)より大きければ、それ以上計算する必要はありません。

i>sqrt(n)の両辺を二乗するとその式になります。

ただ、可読性、計算コストのことを考えて、あまりうまいやり方ではないと思います。改良を考えてみるのもいいかもしれません（根本的に試し割りで計算するのが遅いから、あまり意味はないかもしれませんが・・・）。

Comments

[bbettbn]

平方根の二乗を表現したかったんですね！
ありがとうございました！