約数列挙の高速アルゴリズム[python]

記事内に広告が含まれています。

約数列挙のアルゴリズムについての備忘録です。

$O(\sqrt{N})$の方法

ポイントは2点です。

  • 確認する整数は$1\leq x \leq \sqrt(N)$ まで
  • $x$が$N$の約数ならば、$N/x$も約数
def calc(N):
    res = []
    for i in range(1,N+1):
        #√N 以下だけ確認
        if i*i > N:
            break
        #iがNの約数でない場合
        if N%i !=0:
            continue
        else:
            res.append(i)
            #N÷i　もNの約数
            if N//i != i:
                res.append(N//i)
    
    res.sort()
    return res

print(calc(12)) #[1, 2, 3, 4, 6, 12]

12の場合を考えてみます。

  1. i=1は12の約数。 さらに、12÷1=12も約数。
  2. i=2は12の約数。さらに、12÷2=6 も約数。
  3. i=3は12の約数。さらに、12÷2=4も約数。
  4. i=4は、i*i=16>12より、for文を抜ける。

よって、約数は [1, 2, 3, 4, 6, 12] と求められます。

単純なアルゴリズム $O(N)$

正整数$N$が与えられた際、1以上$N$以下の整数を1つ1つ確認していく方法です。

res = []
for x in range(1, N+1):
    if N%x == 0:
        res.append(x)

まとめ

参考にしたサイト

約数列挙のアルゴリズム | アルゴ式(beta)
algo-method.com
AtCoder 版！マスター・オブ・整数 (素因数分解編) - Qiita
お久しぶりです！アルゴリズムと整数好きのけんちょんです！今回は俗に「数学ゲー」と呼ばれるタイプの問題のうち、整数について語ります。【他シリーズ】AtCoder 版！マスター・オブ・整数 (最…
qiita.com