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 のすべての約数を求めよ。

参考： ABC315 B - Find Divisors

回答　

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 の約数の個数を求めよ。

参考： ABC318 B - Count Divisors

回答　

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 の約数の総和を求めよ。

参考： ABC319 C - Sum of Divisors

回答　

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 番目の約数を出力せよ。

参考： ABC320 B - K-th Divisor

回答　

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)