【C++】素因数分解で約数の和の最小値を求めるアルゴリズムを解説

約数の和の最小値を求める問題とは

この記事では、与えられた整数の「約数の和の最小値」を求めるアルゴリズムを、C++で実装しながら解説します。

例として、数12を考えてみましょう。12は以下のように複数の方法で因数分解できます。

• 12 = 12 × 1 → 和は 12 + 1 = 13
• 12 = 2 × 6 → 和は 2 + 6 = 8
• 12 = 3 × 4 → 和は 3 + 4 = 7
• 12 = 2 × 2 × 3 → 和は 2 + 2 + 3 = 7

この中で最小となる和は7です。本記事では、任意の整数nが与えられたとき、この最小の和を効率よく求める方法を紹介します。

アプローチ：素因数分解すれば和は最小になる

約数の和を最小にするには、数をできるだけ細かく分解する必要があります。言い換えれば、素因数分解を行い、すべての素因数を足し合わせた和Sを求めれば、それが約数の和の最小値になります。

その理由は、2以上の整数aとbの間に常に次の関係が成り立つからです。

a × b ≥ a + b（a = b = 2 のときのみ等号が成立）

つまり、合成数の因数をさらに分解しても和が増えることはなく、多くの場合は減少します。したがって、これ以上分解できない素因数まで分解したときの和が最小値となるのです。

C++による実装例

以下が実際のコードです。試し割り法による素因数分解を用いて、素因数の和を計算しています。

#include <iostream>
using namespace std;

// n を素因数分解し、素因数の総和を返す関数
int primeFactorSum(int n) {
    int s = 0;
    for (int i = 2; i * i <= n; i++) {
        while (n % i == 0) {
            s += i;   // 素因数 i を加算
            n /= i;   // n を i で割り続ける
        }
    }
    if (n > 1) {      // ループ後に残った数も素因数
        s += n;
    }
    return s;
}

int main() {
    int n = 12;
    cout << "約数の和の最小値: " << primeFactorSum(n) << endl;
    return 0;
}

出力結果

約数の和の最小値: 7

コードの解説

• 試し割り法：2から√nまでの整数iで順にnを割り、割り切れる限りiを素因数として加算します。
• 残りの因数の処理：ループ終了後もnが1より大きければ、そのn自体が素因数です（例：12の場合、最後に3が残る）。条件判定なしで加算すると、nが1になった場合（例：n = 4）に余分な1が足されてしまうため、if文での判定が安全です。
• 計算量：√nまで調べればよいため、時間計算量はO(√n)と効率的です。

なお、入力が素数の場合（例：n = 7）は、それ以上分解できないため、その数自身が最小の和になります。

まとめ

整数の約数の和の最小値は、素因数分解によって求められます。「2以上の整数a、bに対して a × b ≥ a + b」という性質を利用すれば、素因数の総和が最小値になることが理解できます。試し割り法を使えばO(√n)で計算できるため、競技プログラミングなどでも役立つテクニックです。