約数の列挙
覚えるための個人的メモ
がとても素晴らしい内容でしたので細かく読み解きます。 正しい内容になるかあまり自信は無いです。
その他参考にした記事
実装
入力した正整数$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つの定理を根拠に実現されています。
- 合成数$N$の素因数($N$の約数となる素数)は全て$\sqrt{N}$以下に存在する(ポイント①, ②)
- 合成数$N$の約数$a$に対して$a \times b = N$となる約数$b$が一意に存在する(ポイント③)
図で表す
(1) $1$~$12$の列
(2) $1$からスタート($12$%$1=0$ なので約数)
(3) $1$の対となる整数は $12/1 = 12$
(4) $2$は$12$の約数, $2$の対となる整数は$12/2 = 6$
(5) $3$は$12$の約数, $3$の対となる整数は$12/3 = 4$
(6) 次は$4$だが、$\sqrt{12} = 3.46$以下の整数3までの探索なので$3$で終わり
計算量・約数の個数
$\sqrt{N}$以下の探索なので計算量は$O(\sqrt{N})$。
約数の個数は、一つの約数を選んだら一意にもう一つ約数が見つかるので最大で$2\sqrt{N}$個となる。