Pythonで2つの数の約数の合計が等しいかどうかを判定する方法

問題概要

2つの整数 p と q が与えられたとき、それぞれの約数の合計が一致しているかどうかを判定する方法を解説します。

例えば、p = 559、q = 703 という入力の場合、出力は True になります。これは、559 の約数が 1, 13, 43、703 の約数が 1, 19, 37 であり、それぞれの合計がどちらも 57 で一致するためです。

アルゴリズムの考え方

この問題を効率的に解くには、以下の手順に従います。

• divSum() 関数を定義します。引数として n を受け取ります。
• total を 1 で初期化し、i を 2 で初期化します。
• i * i <= n を満たす間、次の処理を繰り返します。
  • n が i で割り切れる場合、total に i と floor(n / i)(n を i で割った商の切り捨て値)を加算します。
  • i を 1 増やします。
• total を返します。
• メイン処理では、divSum(p) と divSum(q) が等しければ true を、そうでなければ false を返します。

このアルゴリズムのポイントは、約数を「小さい方と大きい方」のペアとして同時に加算することで、√n まで調べるだけでよい点です。すべての候補を順番に確認する O(n) の素朴な方法と比べ、O(√n) で計算できるため、大きな数でも高速に処理できます。

Pythonによる実装例

from math import floor

def divSum(n):
    total = 1
    i = 2
    while i * i <= n:
        if n % i == 0:
            total += i + floor(n / i)
        i += 1

    return total

def solve(p, q):
    return divSum(p) == divSum(q)

p = 559
q = 703
print(solve(p, q))

入力

559, 703

出力

True

まとめ

約数の合計を求める際、平方根までの範囲だけを走査して約数をペアごとに加算することで、計算量を大幅に削減できます。あとは2つの数それぞれに対してこの関数を適用し、結果を比較するだけで、約数の合計が一致しているかどうかを簡単に判定できます。