C++で最小公倍数（LCM）がNとなる相異なる数の最大合計を求める方法

この記事では、与えられた整数Nに対して、それらの数の最小公倍数（LCM）がNとなるような相異なる数を選んだときの合計の最大値を求めるプログラムを、C++で実装する方法を解説します。

問題の概要

一見複雑に思えるこの問題ですが、実は答えは「Nのすべての約数の合計」になります。なぜなら、Nの約数全体を集めた集合の最小公倍数は必ずNとなり、これ以上大きい合計は得られないからです。したがって、Nの相異なる約数をすべて足し合わせた値が最大合計となります。

具体例を使って問題を確認してみましょう。

入力

N = 12

出力

28

説明

N = 12 の相異なる約数は 1, 2, 3, 4, 6, 12 の6つです。
合計 = 1 + 2 + 3 + 4 + 6 + 12 = 28

解法アプローチ

最もシンプルな解決策は、Nのすべての約数を見つけ出し、それらをすべて加算することです。

ここで重要なのは効率化のポイントです。約数はペアで存在する（例えば12の場合、2と6のような組み合わせ）ため、1から√Nまでの範囲だけでループすれば十分です。具体的には以下の手順で処理します。

• 1から√Nまでの各数iについて、Nがiで割り切れるかどうかを確認します。
• 割り切れる場合、i と N/i が異なるなら、両方を合計に加算します。
• i と N/i が等しい場合（i² = N の場合）、重複を避けるために i を1回だけ加算します。

この手法により、O(√N) の計算量で約数の総和を効率的に求めることができます。

実装例

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

#include <iostream>
using namespace std;
int calcMaxSumForLCM(int N){
    int maxSum = 0;
    for (int i = 1; i*i <= N; i++){
        if (N%i == 0){
            if (i == (N/i))
                maxSum = maxSum + i;
            else
                maxSum = maxSum + i + (N/i);
        }
    }
    return maxSum;
}
int main(){
    int N = 17;
    cout<<"最小公倍数が "<<N<<" となる相異なる数の合計の最大値は "<<calcMaxSumForLCM(N)<<" です";
    return 0;
}

出力

最小公倍数が 17 となる相異なる数の合計の最大値は 18 です

この例ではN=17が素数であるため、約数は1と17のみとなり、合計は18になります。素数の場合は常に「1 + N」という結果になることも覚えておくと良いでしょう。