Pythonで数の因子の最小合計を求めるプログラム｜素因数分解の考え方

本記事では、与えられた整数について、積が元の数と等しくなる因子の組み合わせの中から合計が最小となる値を求める方法を、Pythonのコード例とともに解説します。

問題定義

入力として1つの整数が与えられます。この数を複数の因子の積として表したとき、因子の合計が最小になるケースを求めてください。

すべての因子の組み合わせを網羅的に調べて合計を比較する方法もありますが、実はもっとシンプルで効率的なアプローチが存在します。

考え方：素因数の合計が最小になる

鍵となるのは次の性質です。積が一定の値になるとき、因子の合計が最小になるのは、すべての因子を素数まで分解した場合（素因数分解した場合）です。

これは、2以上の合成数を a × b（a ≥ 2、b ≥ 2）に分解すると、a + b ≤ a × b が常に成り立つためです。つまり、合成数の因子をさらに分解しても積は変わらず、合計は減るか最大でも変わりません。したがって、それ以上分割できない素因数の状態が最適解となります。

例として 12 を考えてみましょう。12 = 6 × 2 のとき合計は 8、12 = 3 × 4 のとき合計は 7、そして 12 = 2 × 2 × 3 と素因数分解したときの合計は 2 + 2 + 3 = 7 となり、これが最小値です。

反復処理による実装例

以下は、試し割り法によって素因数分解を行い、素因数の合計を求めるPythonコードです。

# 反復アプローチによる実装
def findMinSum(num):
    sum_ = 0
    # 2から順に割れるだけ割り、素因数を合計に加算する
    i = 2
    while(i * i <= num):
        while(num % i == 0):
            sum_ += i
            num //= i   # 整数除算で割る
        i += 1
    # ループ終了後に残った数は、それ自体が素因数
    sum_ += num
    return sum_

# 動作確認
num = 12
print(findMinSum(num))

出力

7

コードのポイント

• √num まで試し割り： 外側のループ条件を i * i <= num とすることで、√num 以下の約数だけを調べればよく、計算量を O(√n) に抑えられます。
• 同じ素因数をまとめて処理： 内側の while ループで、同じ素因数で割り切れる限り、加算と除算を繰り返します。
• 残った数の処理： ループ終了時に 1 より大きい数が残っていれば、それは √num より大きい素因数なので、そのまま合計に加えます。
• 整数除算を使用： Python 3 では / は浮動小数点除算になるため、// を使うことで正確な整数演算が行えます。

まとめ

本記事では、数の因子の最小合計を求める問題に対して、素因数分解を利用した効率的な解法を紹介しました。「積が固定なら、素因数の和が最小になる」という性質を理解すれば、全探索を行わずとも O(√n) の計算量で答えを得られます。ぜひご自身のコードにも応用してみてください。