【Python】合計がNに等しく積が最大となる4つの約数を見つけるプログラム（セット2）

ある数 N が与えられたとき、N のすべての約数を求め、以下の条件を満たす4つの約数の積を返すことを考えます。

• 4つの約数の合計が N と等しいこと
• 4つの約数の積が最大であること
• 積を最大化するため、4つの約数は互いに同じ値でも構わない

問題例

たとえば入力が N = 60 の場合、出力は次のようになります。

• すべての約数：1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60
• 最大の積：50625

この場合、15 を4回選ぶことで積が最大になります（15 × 15 × 15 × 15 = 50625、かつ 15 × 4 = 60）。

解法のアプローチ

この問題は、次の手順で解くことができます。

1. 空のリスト factors を用意します。
2. i を 1 から √n の整数部分 + 1 まで繰り返し、n が i で割り切れる場合は i と n // i の両方をリストに追加します（これにより約数を効率よく列挙できます）。
3. リストをソートして表示します。
4. final_prod = 1、flag = 1 として初期化します。
5. 三重ループで約数の組み合わせ (i, j, k) を調べ、残りの値 y = n - factors[i] - factors[j] - factors[k] を計算します。
6. y が 0 以下になったらループを抜けます。
7. y が n の約数であれば flag = 0 とし、積 factors[i] * factors[j] * factors[k] * y が現在の最大値より大きければ更新します。
8. 最後に、有効な組み合わせが見つかった場合（flag == 0）は最大の積を表示し、見つからなければ「Not possible」を表示します。

実装例

それでは、実際の Python コードを見てみましょう。

from math import *

def get_factors(n):
    factors = []
    for i in range(1, int(sqrt(n)) + 1):
        if n % i == 0:
            factors.append(i)
            factors.append(n // i)
    factors.sort()
    print("Factors are", factors)

    final_prod = 1
    flag = 1
    for i in range(0, len(factors)):
        for j in range(i, len(factors)):
            for k in range(j, len(factors)):
                y = n - factors[i] - factors[j] - factors[k]
                if y <= 0:
                    break
                if n % y == 0:
                    flag = 0
                    final_prod = max(factors[i] * factors[j] * factors[k] * y, final_prod)
    if flag == 0:
        print("Product is", final_prod)
    else:
        print("Not possible")

n = 60
get_factors(n)

入力

60

出力

Factors are [1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60]
Product is 50625

計算量について

約数の列挙は O(√n) で行えますが、その後の三重ループによる組み合わせ探索は約数の個数を m とすると O(m³) かかります。そのため、N が非常に大きい場合や約数の個数が多い場合は実行時間が長くなる点に注意が必要です。ただし、y ≤ 0 になった時点で内側のループを打ち切ることで、無駄な計算を削減しています。