たけし備忘録

自分の好奇心の赴くままに勉強メモ LL系が大好き Python bash Julia C

約数の列挙

覚えるための個人的メモ

qiita.com

がとても素晴らしい内容でしたので細かく読み解きます。 正しい内容になるかあまり自信は無いです。

その他参考にした記事

やさしい整数論

実装

入力した正整数$N$の約数をリストで出力します。

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)
    return divisors

make_divisors(12)

[1, 12, 2, 6, 3, 4]

ポイント

ポイント①、②、③を解説します。

ポイント①

1 から $\sqrt{N}$までの整数を列挙します。

for i in range(1, int(n**0.5)+1): # ポイント①

ポイント②

1 から $\sqrt{N}$までの各整数$i$が 元の整数$N$で割り切れる(=$N$の約数) か判定する

if N % i == 0: # ポイント②
        divisors.append(i)

ポイント③

$i$が$N$の約数のとき、$N//i$もまた$N$の約数である
ただし $N$が平方数(12*12=144など)の場合に重複してリストに追加してしまうため、if文で$i$が$N$の平方根ではない場合のみリストに追加する。

if i != N // i: # ポイント③
        divisors.append(N//i)

理論

上記の約数列挙は以下の2つの定理を根拠に実現されています。

  1. 合成数$N$の素因数($N$の約数となる素数)は全て$\sqrt{N}$以下に存在する(ポイント①, ②)
  2. 合成数$N$の約数$a$に対して$a \times b = N$となる約数$b$が一意に存在する(ポイント③)

図で表す

(1) $1$~$12$の列 f:id:takeshiD:20190929112221p:plain

(2) $1$からスタート($12$%$1=0$ なので約数) f:id:takeshiD:20190929112234p:plain

(3) $1$の対となる整数は $12/1 = 12$ f:id:takeshiD:20190929112249p:plain

(4) $2$は$12$の約数, $2$の対となる整数は$12/2 = 6$ f:id:takeshiD:20190929112302p:plain

(5) $3$は$12$の約数, $3$の対となる整数は$12/3 = 4$ f:id:takeshiD:20190929112343p:plain

(6) 次は$4$だが、$\sqrt{12} = 3.46$以下の整数3までの探索なので$3$で終わり f:id:takeshiD:20190929112354p:plain

計算量・約数の個数

$\sqrt{N}$以下の探索なので計算量は$O(\sqrt{N})$。
約数の個数は、一つの約数を選んだら一意にもう一つ約数が見つかるので最大で$2\sqrt{N}$個となる。