約数を高速で列挙するコードです(計算量$O(\sqrt{N})$)
問題の制約が$10^9$でも間に合います。
ほぼ自分用のメモとして投稿
(@yucatioさんの指摘を受け,小さい約数のリストと大きい約数のリストを最後に結合する方法に変えました.)
コード
def make_divisors(n):
lower_divisors , upper_divisors = [], []
i = 1
while i*i <= n:
if n % i == 0:
lower_divisors.append(i)
if i != n // i:
upper_divisors.append(n//i)
i += 1
return lower_divisors + upper_divisors[::-1]