1.1.1. 約数列挙

Code: multiple_and_divisor.py

Test: test_multiple_and_divisor.py

約数とは

整数 \(n\) を割り切る整数のこと。

例えば \(n=12\) のとき、約数は \(1, 2, 3, 4, 6, 12\) である。

実装

概要

試し割り法 (Wikipedia)

約数を列挙する。区間 \([1, n]\) の整数を使って実際に \(n\) を割ってみる。

実装のポイント

\(n\) を \(a\) で割り切れるか試すとき、同時に \(n/a\) が得られる。これも \(n\) の約数となる。

そのため、実際には 区間 \([1, \sqrt{n}]\) に含まれる整数だけを試せば十分。

計算量

• list_divisors(n, sorted=False) \(\mathcal{O}(\sqrt{n})\)

コード

from __future__ import annotations


def list_divisors(n: int, sorted: bool = False) -> list[int]:
    divisors = []
    i = 1
    while i * i <= n:
        if n % i == 0:
            divisors.append(i)
            if i * i != n:
                divisors.append(n // i)
        i += 1
    if sorted:
        divisors.sort()
    return divisors

使用例

divisors = list_divisors(12)
print(divisors)

[1, 12, 2, 6, 3, 4]

divisors = list_divisors(12, sorted=True)
print(divisors)

[1, 2, 3, 4, 6, 12]