C++でNを約数で繰り返し除算した際の最大合計を求める方法

問題概要

この問題では、整数 N が与えられます。求めるのは、N を約数で繰り返し除算していったときに得られる値の合計の最大値です。C++ を使ってこの計算を行うプログラムを作成します。

アルゴリズムの考え方

基本的な方針は次のとおりです。

• 数値 N を 1 になるまで繰り返し除算する。
• 各ステップで現れる値（元の数と商）をすべて合計する。
• 合計を最大化するために、毎回最小の約数で割る。

なぜ最小の約数で割るのが最適なのでしょうか。それは、最小の約数で割ると各ステップでの商が最も大きくなり、途中の値が高い水準を保てるためです。結果として、合計も最大になります。

入出力例

入力： N = 12

出力： 22

説明： 数値を再帰的に除算しながら合計を求めます。

除算 1: 12 / 2 = 6
除算 2: 6 / 2 = 3
除算 3: 3 / 3 = 1
合計 = 12 + 6 + 3 + 1 = 22

C++による実装例

以下は、この解法の動作を示すサンプルプログラムです。

#include <bits/stdc++.h>
using namespace std;
int smallestDivisor(int n){
    int mx = sqrt(n);
    for (int i = 2; i <= mx; i++)
        if (n % i == 0)
            return i;
    return n;
}
int calculateMaxSum(int n) {
    long long maxSum = n;
    while (n > 1) {
        int divisor = smallestDivisor(n);
        n /= divisor;
        maxSum += n;
    }
    return maxSum;
}
int main(){
    int N = 12;
    cout<<"The maximum sum after repeatedly dividing "<<N<<" by divisor is "<<calculateMaxSum(N);
    return 0;
}

コードの解説

• smallestDivisor 関数： 2 から √n まで順に試し割りを行い、最初に見つかった約数（＝最小の約数）を返します。約数が見つからなければ、その数自身（素数の場合）を返します。
• calculateMaxSum 関数： 初期値として N 自身を合計に加え、N が 1 になるまで最小の約数で割り続けながら、各ステップの商を合計に加算していきます。

計算量は、1 回の最小約数探索が O(√n)、全体でも十分高速に動作するため、大きな N に対しても実用的です。

実行結果

The maximum sum after repeatedly dividing 12 by divisor is 22

まとめ

この問題のポイントは、「毎回最小の約数で割ることで、途中の値をできるだけ大きく保つ」という貪欲的な戦略にあることが分かります。シンプルな試し割り法とループ処理を組み合わせるだけで、効率的に最大合計を求めることができます。