Pythonにおける約数の高速列挙の解説

ここでは Qiita で @LorseKudos さんが紹介している

qiita.com

を自分の備忘録としても紹介，解説していきたいと思います。

競技プログラミングをやっているときに約数の列挙の作業が求められることがかなりの頻度であります。簡単に約数の列挙を行おうと思えば sympy をインポートして

import sympy
sympy.divisors(n)

これで出せます。ただし，競技プログラミングでは sympy が使えないのでこの方法が使えません。そこで今回は先ほどのサイトで @LorseKudos さんが紹介して下さっている次のコードを用いることで，競技プログラミングでも約数の列挙を高速に行うことができます。

def make_divisors(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

ただ，なぜこれで約数が列挙できるのか分かりにくいかと思いますので（少なくとも私は理解するのにかなり時間がかかりました😅）説明していきます。

まず３行目。なぜ探索する範囲が

range(1, int(n**0.5)+1)

で良いのかについてです。i <= j として i，j を n の約数としたとき，
n = i × j
の関係が成り立ちますよね。そうすると，i は √n 以下でなければなりません。
どちらも √n 以上であれば，i × j >= √n × √n = n となってしまいます。
なので少なくとも１から √n の範囲で探索をしてあげれば良いわけです。もし i が n の約数であることが分かれば，j も n から i を割ってあげることで出せますよね。
よって，４，５行目はこの範囲の i において以下の作業を行っています。

if n % i == 0:
    divisors.append(i)

これは，もし i が n で割り切れる（＝ n の約数）なら，約数の要素に i を追加するというものです。
さらに同時にこの約数 i が特定された後に次の分岐を行っています。

if i != n // i:
    divisors.append(n//i)

これは先ほどの j を約数の要素に追加するものです。
if 分岐は，i が n の平方根であった時に約数のダブりを無くすための分岐です。つまり i=√n だったとき，
n = i × j = √n × √n
となり，i = j となるので，このまま j を約数の要素に加えてしまうと，√n が二回カウントされてしまいますよね。
j と i が同じ値でないことが確認されたのち，j = n ÷ i なのでその値を約数の要素に追加しているわけです。
j は int 型にしたいので n//i として追加しています。

最終的に divisors に格納された約数の要素を返すようにすれば，これで約数を列挙できたことになります。
１～√n までの探索なので，O(√n)で約数列挙をすることができます。👍
ただしこのままでは順番がバラバラなので，ソートしなければならないときは９行目のソートをすればいいわけです。

いかがでしょうか。
このような仕組みでこのコードが成り立っているわけです。
もし何かあればぜひコメントよろしくお願いします！
それでは！