Atcoder Biggner Contest 180 C問題

初めに

昨日C問題を解いてて詰まったところをまとめようと思います

C:Cream puff

問題
N個のシュークリームがあります。シュークリームを分割することなく平等に分けることができるような人数としてあり得るものを全て求めてください。
$条件:1≤N≤10^{12}$

初めに以下のコードで実行したのですが当然TLE

test.py

N = int(input())
for i in range(1,N+1):
    if N%i==0:
        print(i)

解法について

この問題は言い換えると「Nの約数を列挙する」ことと同値になります。なので1~Nまでの正の整数でNが割り切れるかどうかを判定すればよいことになります。しかし今回条件よりNが$N^{12}$までという条件なので普通に実装すれば時間が$O(n)$となるので時間切れになります。そこでAtCoder 版！マスター・オブ・整数 (素因数分解編) の記事を参考にしたところどうやら$\sqrt{N}$まで調べればよさそうです。なのでコードを

test.py

import math
N = int(input())
num = []
for i in range(1,math.sqrt(N+1)):
    if N%i==0:
        num.append(i)
        if i != N//i: #iとついになる約数
            num.append(i)
num.sort() #小さい順に並べ替え
for j in num:
    print(j)

以上のようにすればよさそうです。これにすることで$O(\sqrt{N})$の時間で済みそうです。