【C++】数値Nの4つの因数の積を最大化する方法

この記事では、与えられた整数 N に対して、4つの因数 A・B・C・D の積が最大となる組み合わせを求める問題を解説します。ただし、次の条件を満たす必要があります。

4つの因数の合計が N と等しいこと、すなわち N = A + B + C + D であること。

具体例

例1

• 入力： N = 10
• 出力： 20

説明： 10の因数は 1, 2, 5, 10 です。5 × 2 × 2 × 1 = 20 のとき積が最大となり、条件 5 + 2 + 2 + 1 = 10 も同時に満たしています。

例2

• 入力： N = 16
• 出力： 256

説明： 16の因数は 1, 2, 4, 8, 16 です。4 × 4 × 4 × 4 = 256 のとき積が最大となり、条件 4 + 4 + 4 + 4 = 16 も満たしています。

アルゴリズムの考え方

このプログラムでは、以下の手順で最大の積を求めます。

1. int型の配列 Factors[] を用意し、与えられた数の因数を格納します。また、配列に格納された要素数を管理するための変数 K = 0 を用意します。
2. 与えられた数の因数をすべて求める関数 FindFactors() を作成します。
3. i = 1 から i * i <= N の間、ループを回します。
4. ループ内で N % i == 0 かどうかを判定し、i が因数であるかを確認します。
5. i が因数の場合、N / i == i かどうかをチェックします。真であれば i のみを Factors[] に格納し、そうでなければ N / i と i の両方を格納します（平方根で重複を避けるため）。
6. 因数の中から最大の積を見つける関数 Product() を作成します。
7. product = 0 および size = K + 1 を初期化します。
8. 4重のネストしたループを用意し、それぞれ size まで繰り返します。
9. ループ内で sum = Factors[i] + Factors[j] + Factors[k] + Factors[l] を計算します。
10. sum == N であれば、pro = Factors[i] * Factors[j] * Factors[k] * Factors[l] を求めます。
11. pro > product であれば、product = pro として更新します。
12. 最後に product を返します。

なお、この手法の計算量は因数の個数を K とすると O(K⁴) となります。N が大きくなると処理時間が増加するため、より効率的な解法としては「4つの数をできるだけ均等に近づけると積が最大化される」という数学的性質（相加平均・相乗平均の関係）を利用する方法もあります。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
// 因数を格納する配列
int Factors[30];
int K = 0;
// 因数を求める関数
int FindFactors(int N){
    // i が sqrt(N) に達するまでループ
    for (int i = 1; i * i <= N; i++){
        if (N % i == 0){
            /* 両方の因数が同じ場合は1つだけ格納 */
            if ((N / i) == i){
                Factors[K] = i;
                K++;
            }
            else{
                // 1つ目の因数を配列に格納
                Factors[K] = N / i;
                K++;
                // 2つ目の因数を配列に格納
                Factors[K] = i;
                K++;
            }
        }
    }
}
// 最大の積を求める関数
int Product(int N){
    int product = 0;
    int size = K + 1;
    for (int i = 0; i < size; i++)
        for (int j = 0; j < size; j++)
            for (int k = 0; k < size; k++)
                for (int l = 0; l < size; l++){
                    // 各因数の組み合わせの和を計算
                    int sum = Factors[i] + Factors[j] + Factors[k] + Factors[l];
                    // 和が N と等しいか確認
                    if (sum == N){
                        // 因数の積を計算
                        int pro = Factors[i] * Factors[j] * Factors[k] * Factors[l];
                        // より大きな値が見つかったら更新
                        if(pro > product)
                            product = pro;
                    }
                }
    return product;
}
// メイン関数
int main(){
    int N = 10;
    // N の因数を求める関数を呼び出し
    FindFactors(N);
    // 最大の積を求める関数を呼び出し
    cout<<Product(N);
    return 0;
}

実行結果

上記のコードを実行すると、次の出力が得られます。

20

N = 10 の場合、5 × 2 × 2 × 1 = 20 が条件を満たす最大の積となるため、正しく 20 が出力されています。