数の因子の最小合計を求めるC++プログラムの解説

本記事では、ある整数を複数の因子（約数）の積に分解したとき、その因子の合計が最小となる値を求めるプログラムについて解説します。すべての因子の組み合わせを列挙して比較する必要があるように思えますが、実は素因数分解を利用することで、効率的に答えを求められます。

入力：n = 12
出力：7

考え方

まず数nの因子を見つけて合計を求め、その合計を最小化することを目指します。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

ここで重要なのは、合成数の因子をさらに小さな因子へ分解しても、合計が増えることはないという点です。例えば「6」をひとつの因子とみなすよりも「2 × 3」に分解したほうが合計は小さくなります（6 → 5）。したがって、これ以上分割できない素因数まで分解したときの素因数の和こそが、求めるべき最小の合計になります。

実装例

#include<iostream>
using namespace std;
int main() {
    int n = 12;
    int sum = 0;
    for (int i = 2; i * i <= n; i++) {
        while (n % i == 0) {
            sum += i;
            n /= i;
        }
    }
    sum += n;
    cout << sum;
    return 0;
}

コードの解説

このプログラムは素因数分解のアルゴリズムを利用しています。2から順に、√n以下の整数iでnを割り切れる限り割り続け、そのたびにiを合計に加算していきます。試し割りが終わった後に残ったnが1より大きければ、それは最後の素因数なので合計に加えます。

試し割りは√nまで確認すれば十分であるため、このアルゴリズムの計算量はO(√n)となります。すべての因子の組み合わせを総当たりで調べる方法と比べて、はるかに高速に動作するのが特徴です。