Pythonで約数を列挙する方法について

Pythonで「約数を列挙する方法」は、基本から応用まで様々なアプローチが可能です。

ここでは、初心者向けのシンプルな方法から、高速なアルゴリズム、さらには応用テクニックまでを、段階的かつ丁寧に解説します。

基本：for文を使ったシンプルな方法

まずは、「1からnまで順に割って、割り切れるかチェックする」という基本中の基本の方法です。

例：36の約数を列挙する

n = 36
for i in range(1, n + 1):
    if n % i == 0:
        print(i)

解説

• range(1, n+1) で 1 から n までループ
• n % i == 0 なら約数と判断
• 時間計算量：O(n)（大きなnでは遅くなる）

高速化：平方根までで十分な理由

実は、約数は必ずペアで現れるという性質があります。

例えば、36の約数は

• 1 × 36
• 2 × 18
• 3 × 12
• 4 × 9
• 6 × 6（ここで折り返し）

このため、√n まで調べれば、すべての約数ペアを見つけられます。

実装例

import math

n = 36
divisors = []

for i in range(1, int(math.isqrt(n)) + 1):
    if n % i == 0:
        divisors.append(i)
        if i != n // i:  # 自分と同じ数（√n）でない場合はペアも追加
            divisors.append(n // i)

divisors.sort()
print(divisors)

特徴

• 時間計算量：O(√n) → 非常に高速
• ソートが必要（順番を揃えたい場合）

関数化して再利用しやすくする

再利用性を高めるために関数にしておきましょう。

def list_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)
    return sorted(divisors)

print(list_divisors(60))  # [1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60]

応用例：複数の整数の共通約数を求めたい

Pythonのmath.gcd()を使って、2つの整数の最大公約数をまず求め、その最大公約数の約数を列挙すれば、共通約数になります。

import math

def common_divisors(a, b):
    g = math.gcd(a, b)
    return list_divisors(g)

print(common_divisors(36, 60))  # [1, 2, 3, 6, 12]

まとめ

方法	時間計算量	特徴
for で1から順に試す	O(n)	一番直感的。コードはシンプル
√nまで + ペア利用	O(√n)	実用的かつ高速。よく使われる
約数関数の応用	O(√n)	再利用性が高く、他の処理と組み合わせやすい

おまけ

import numpy as np

n = 36
divisors = np.arange(1, n+1)
print(divisors[n % divisors == 0])

シンプルですが、大きな数には不向きです。

学習目的での使用にとどめるのがよいでしょう。

以上、Pythonで約数を列挙する方法についてでした。

最後までお読みいただき、ありがとうございました。