約数を高速で列挙するコード(Python)

約数を高速で列挙するコードです(計算量$O(\sqrt{N})$)

問題の制約が$10^9$でも間に合います。

ほぼ自分用のメモとして投稿


コード

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

6行目のif文は$N$が平方数のときに$\sqrt{N}$を2個出力しないようにするためのものです。

また、このままだと出力される約数の順番はバラバラなのでソートしなければいけない場合は9行目をアンコメントしてください。約数の個数は高々$2\sqrt{N}$個でソートの計算量は$O(\sqrt{N}\log N)$なので、制限時間を超えることはありません。


もっと簡単な方法(競プロでは非推奨)

import sympy

sympy.divisors(10**9)

これが最も簡単に約数を求める方法だと思います。計算量も$O(\sqrt{N})$です。

しかし、競プロではsympyが使えない場合が多い(少なくともAtCoderでは使えない)のでこの方法は使えません。

競プロ以外で約数を求めるときはこちらを使うといいのではないでしょうか。