Pythonで閉区間[2, n]に含まれるすべての完全数を見つけて出力する方法

完全数とは？

完全数とは、その数自身を除く約数（真の約数）の総和が、その数自身とちょうど等しくなる正の整数のことです。最も小さい完全数は 6 で、6 = 1 + 2 + 3 が成り立ちます。次に小さい完全数は 28（28 = 1 + 2 + 4 + 7 + 14）であり、その後は 496、8128 と続きます。

Pythonで範囲内の完全数を求める手順

指定した閉区間 [start, end] 内の各整数に対して、以下の手順で判定を行います。

1. 1 からその数未満までの整数を順に調べ、約数だけを合計する。
2. 合計が元の数自身と一致していれば、それは完全数である。

サンプルコード

def print_perfect_nums(start, end):
    for i in range(start, end + 1):
        total = 0
        for x in range(1, i):
            # 約数であれば合計に加算する
            if i % x == 0:
                total += x
        # 約数の総和が自分自身と一致すれば完全数
        if total == i:
            print(i)

print_perfect_nums(2, 300)

実行結果

このコードを実行すると、次のように出力されます。

6
28

コードのポイント

• 外側のループで範囲内の各数値を1つずつ取り出し、内側のループでその約数をすべて足し合わせます。
• i % x == 0 は「x が i の約数である」ことを意味します。
• 比較 total == i は内側のループが完了した後に行うのが重要です。ループの途中で比較すると、約数の部分和がたまたま一致してしまう過剰数（例：24）まで誤って検出されるおそれがあります。

処理速度を改善するには

上記の方法は分かりやすい反面、各数値について 1 から順に調べるため全体の計算量が O(n²) になります。約数はペアで現れる（x が約数なら i ÷ x も約数）という性質を利用し、√i までだけ調べてペアを同時に加算すれば、大幅な高速化が可能です。

import math

def print_perfect_nums_fast(start, end):
    for i in range(max(start, 2), end + 1):
        total = 1  # 1 は必ず約数
        for x in range(2, math.isqrt(i) + 1):
            if i % x == 0:
                total += x
                pair = i // x
                if pair != x:
                    total += pair
        if total == i:
            print(i)

print_perfect_nums_fast(2, 10000)

この改良版を実行すると、10000 以下の完全数として 6、28、496、8128 の4つが出力されます。