約数列挙
Abstract
正整数$ Nの約数を列挙するには, $ 1から$ \lfloor \sqrt{N} \rfloorまで順に割り切れるかどうかをチェックしていけばよい. 計算量は$ O(\sqrt{N})time.
Explanation
愚直に試し割りをすることで, 正整数$ Nの約数を列挙できる.
Algorithm (約数列挙)
Input:
正整数$ N
Output:
$ Nの約数の集合$ D_{N}
1. $ D_N \gets \varnothing, $ n = 1と初期化する.
2. $ n^2 \le Nである間, 以下を繰り返す.
2-1. $ Nを$ nで割った商$ qとあまり$ rを求める.
2-2. $ r = 0であれば, $ D_N \gets D_N \cup \{ n \}とする. さらに, $ q \neq nであれば, $ D_N \gets D_N \cup \{ q \}とする.
2-3. $ n \gets n + 1と更新する.
3. $ D_Nを出力する.
Implementation
上のアルゴリズムのとおり組むだけ.
Input
正整数 n
Output
n の約数からなるリスト lst
Time complexity
$ O(\sqrt{N})time.
code:python
def divisors(n):
lst = []; i = 1
while i ** 2 <= n:
q, r = divmod(n, i)
if r == 0:
lst.append(i)
if i != q: lst.append(q)
i += 1
return lst
Verification
References