約数列挙のアルゴリズムについての備忘録です。
$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の場合を考えてみます。
i=1
は12の約数。 さらに、12÷1=12も約数。i=2
は12の約数。さらに、12÷2=6 も約数。i=3
は12の約数。さらに、12÷2=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)
まとめ
参考にしたサイト
![](https://output-zakki.com/wp-content/uploads/cocoon-resources/blog-card-cache/4f5a0762fc5cf0ef129be64817365b44.jpg)
約数列挙のアルゴリズム | アルゴ式(beta)
![](https://qiita-user-contents.imgix.net/https%3A%2F%2Fcdn.qiita.com%2Fassets%2Fpublic%2Farticle-ogp-background-9f5428127621718a910c8b63951390ad.png?ixlib=rb-4.0.0&w=1200&mark64=aHR0cHM6Ly9xaWl0YS11c2VyLWNvbnRlbnRzLmltZ2l4Lm5ldC9-dGV4dD9peGxpYj1yYi00LjAuMCZ3PTkxNiZoPTMzNiZ0eHQ9QXRDb2RlciUyMCVFNyU4OSU4OCVFRiVCQyU4MSVFMyU4MyU5RSVFMyU4MiVCOSVFMyU4MiVCRiVFMyU4MyVCQyVFMyU4MyVCQiVFMyU4MiVBQSVFMyU4MyU5NiVFMyU4MyVCQiVFNiU5NSVCNCVFNiU5NSVCMCUyMCUyOCVFNyVCNCVBMCVFNSU5QiVBMCVFNiU5NSVCMCVFNSU4OCU4NiVFOCVBNyVBMyVFNyVCNyVBOCUyOSZ0eHQtY29sb3I9JTIzMjEyMTIxJnR4dC1mb250PUhpcmFnaW5vJTIwU2FucyUyMFc2JnR4dC1zaXplPTU2JnR4dC1jbGlwPWVsbGlwc2lzJnR4dC1hbGlnbj1sZWZ0JTJDdG9wJnM9ZThiZTE2ZmNlOTIyYzE5NjY5M2IwYmE1YTAxMGZkMDU&mark-x=142&mark-y=112&blend64=aHR0cHM6Ly9xaWl0YS11c2VyLWNvbnRlbnRzLmltZ2l4Lm5ldC9-dGV4dD9peGxpYj1yYi00LjAuMCZ3PTcxNiZ0eHQ9JTQwZHJrZW4lMjBpbiUyMCVFNiVBMCVBQSVFNSVCQyU4RiVFNCVCQyU5QSVFNyVBNCVCRU5UVCVFMyU4MyU4NyVFMyU4MyVCQyVFMyU4MiVCRiVFNiU5NSVCMCVFNyU5MCU4NiVFMyU4MiVCNyVFMyU4MiVCOSVFMyU4MyU4NiVFMyU4MyVBMCZ0eHQtY29sb3I9JTIzMjEyMTIxJnR4dC1mb250PUhpcmFnaW5vJTIwU2FucyUyMFc2JnR4dC1zaXplPTMyJnR4dC1hbGlnbj1sZWZ0JTJDdG9wJnM9MzI1ZDEzNDQzM2UzOTY0Nzg2YTExZDA2MjczNDIwZTA&blend-x=142&blend-y=491&blend-mode=normal&s=6311edd014aa5144736ea61f69e16b9b)
AtCoder 版!マスター・オブ・整数 (素因数分解編) - Qiita
お久しぶりです!アルゴリズムと整数好きのけんちょんです!今回は俗に「数学ゲー」と呼ばれるタイプの問題のうち、整数について語ります。【他シリーズ】AtCoder 版!マスター・オブ・整数 (最…