1.1.2. 倍数列挙¶

Code: multiple_and_divisor.py

Test: test_multiple_and_divisor.py

倍数とは¶

\(a\) の倍数は、\(a\) を整数倍した数として定義される。

\[\cdots, -3a, -2a, -a, 0, a, 2a, 3a, \cdots\]

実装¶

概要¶

区間 \([0, n]\) に含まれる倍数を列挙する。

実装のポイント¶

\(a\) から始めて \(a\) ずつ足していけばよい。\(n\) 以下の \(a\) の正の倍数は \(\lfloor \frac{n}{a} \rfloor\) 個なので、\(a\) が大きいほど短時間で列挙できる。

計算量¶

list_multiples(n, a) \(\mathcal{O}(\frac{n}{a})\)

コード¶

[1]:

from __future__ import annotations


def list_multiples(a: int, n: int) -> list[int]:
    multiples = []
    for a in range(a, n+1, a):
        multiples.append(a)
    return multiples

使用例¶

[2]:

multiples = list_multiples(3, 24)
print(multiples)

[3, 6, 9, 12, 15, 18, 21, 24]