Overview
約数列挙（Divisor Enumeration） は、整数 N のすべての約数を求める基本的な数論アルゴリズム。
1.約数列挙の基本
2.約数列挙の応用
3.典型問題を解いてみる
1. 約数列挙の基本
約数の定義
整数 $N$ の 約数 とは、$N$ を割り切ることができる整数 のこと。
例：
$N=12$ の場合、約数は {1, 2, 3, 4, 6, 12}
$N=17$ の場合、約数は {1, 17}（素数）
(1) すべての整数を試す方法（O(N）)
一番単純な方法は、1 から $N$ までのすべての数で割り切れるかを確認する方法。
def divisors_naive(n):
result = []
for i in range(1, n + 1):
if n % i == 0:
result.append(i)
return result
print(divisors_naive(12)) # 出力: [1, 2, 3, 4, 6, 12]
- 時間計算量は O(N)（すべての数を試すため）
- 小さな数には問題ないが、大きな N では非効率
(2) √N まで調べる効率的な方法（O(√N）)
約数は対になって現れるため、$i$ について 1 から $\sqrt{N}$まで調べるだけで十分。
＜アルゴリズムの考え方＞
もし $i $が $N $の約数なら、$\frac{N}{i}$も約数
例：
$N=12$ の場合
$1$ は約数 → $\frac{12}{1} = 12$も約数
$2$ は約数 → $\frac{12}{2} = 6$も約数
$3$ は約数 → $\frac{12}{3} = 4$も約数
$\sqrt{12} ≈ 3.46$ なので 1〜3 まで調べればよい
<実装>
import math
def divisors_efficient(n):
result = []
for i in range(1, int(math.sqrt(n)) + 1):
if n % i == 0:
result.append(i)
if i != n // i: # 重複を防ぐ
result.append(n // i)
return sorted(result)
print(divisors_efficient(12)) # 出力: [1, 2, 3, 4, 6, 12]
- 時間計算量$ O(√N) （平方根までしか調べないため、高速）
-
i != n // iの条件で、平方数の重複を防ぐ - 約数はソートしておくと使いやすい
2. 約数列挙の応用
(1) 約数の個数を求める
約数の個数を求める場合、上記の divisors_efficient() の len(result) を取るだけで OK。
def count_divisors(n):
count = 0
for i in range(1, int(math.sqrt(n)) + 1):
if n % i == 0:
count += 1
if i != n // i:
count += 1
return count
print(count_divisors(12)) # 出力: 6（約数の個数）
(2) 約数の総和を求める
def sum_of_divisors(n):
total = 0
for i in range(1, int(math.sqrt(n)) + 1):
if n % i == 0:
total += i
if i != n // i:
total += n // i
return total
print(sum_of_divisors(12)) # 出力: 28（1+2+3+4+6+12）
3. 典型問題を解いてみる
例題1. 約数列挙
問題: N のすべての約数を求めよ。
回答
import math
N = int(input())
result = []
for i in range(1, int(math.sqrt(N)) + 1):
if N % i == 0:
result.append(i)
if i != N // i:
result.append(N // i)
print(*sorted(result))
例題2. 約数の個数を求める
問題: N の約数の個数を求めよ。
回答
import math
N = int(input())
count = 0
for i in range(1, int(math.sqrt(N)) + 1):
if N % i == 0:
count += 1
if i != N // i:
count += 1
print(count)
例題3. 約数の総和を求める
問題: N の約数の総和を求めよ。
回答
import math
N = int(input())
total = 0
for i in range(1, int(math.sqrt(N)) + 1):
if N % i == 0:
total += i
if i != N // i:
total += N // i
print(total)
例題4. K 番目の約数を求める
問題: N の約数を昇順で列挙し、K 番目の約数を出力せよ。
回答
import math
N, K = map(int, input().split())
result = []
for i in range(1, int(math.sqrt(N)) + 1):
if N % i == 0:
result.append(i)
if i != N // i:
result.append(N // i)
result.sort()
print(result[K-1] if K <= len(result) else -1)