pythonでの約数の高速列挙

Question

前提・実現したいこと

競技プログラミングをするときに約数の高速列挙が必要になり，以下のサイトを見つけました。
約数を高速で列挙するコード(Python)
ただ，このコードでなぜ約数の列挙ができるのかが理解できません。
まずなぜ範囲が１～int(n^0.5)でいいのでしょうか。
また，６行目のnが平方根の時の処理も良く分かりません。
何か前提知識があるのなら，それも踏まえて教えてください。
よろしくお願いします。

該当のソースコード

    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

Answer 1

まずなぜ範囲が１～int(n^0.5)でいいのでしょうか。

n = i * jのように書けるなら、iかjの小さい方はnの平方根以下になります（「両方が平方根より大きい」となれば、その2つをかけるとnより大きくなります）。

６行目のnが平方根の時の処理も良く分かりません。

いえ、これは「平方根でない時」の処理です。n = i * jとしたiとjの両方を追加しています。

Comments

[maisumakun]

なお、細かい素因数がたくさんあるような、全体としては大きい値について約数列挙を行いたい場合、この方法より素因数分解しながら進めるほうが効率的かと思います。

[tam1006]

大変よく分かりました！
助かりました，ありがとうございます。