C++で合計がNに等しく積が最大となるNの4つの約数を求める方法

概要

整数 N が与えられたとき、次の条件を満たす N の4つの約数を見つけ、それらの積を出力することを考えます。

• 4つの約数の合計が N に等しいこと。
• 4つの約数の積が最大であること。

もし条件を満たす4つの約数が存在しない場合は「Not possible(不可能)」と出力します。

なお、積を最大化するためには、4つの約数がすべて同じ値であっても構いません。

入力例

80

出力例

All the factors are -> 1 2 4 5 8 10 16 20 40 80
Product is -> 160000

この例では、約数 20 を4回選択しています。したがって、20 + 20 + 20 + 20 = 80 となり、このとき積 20 × 20 × 20 × 20 = 160000 が最大になります。

アルゴリズム

この問題を解くための手順は以下の通りです。

• まず、1 から N の平方根まで順に調べ、「i」と「n/i」が N を割り切るかどうかを確認し、約数をベクトル(vector)に格納します。
• 次に、ベクトルをソートし、すべての要素を出力します。
• 3重ループを実装し、4つ目の数と組み合わせたときに積が最大になる3つの数を決定します。
• より大きな積が見つかるたびに、以前の最大積を新しい値で置き換えます。
• 4つの約数が見つかった時点で積を出力します。

C++による実装例

// C++プログラム: 合計がNに等しく積が最大となる
// Nの4つの約数を見つける
#include <bits/stdc++.h>
using namespace std;

// 約数を求め、その4つを出力する関数
void findfactors2(int n1){
    vector<int> vec2;
    // すべての約数をベクトルに格納する
    for (int i = 1; i * i <= n1; i++) {
        if (n1 % i == 0) {
            vec2.push_back(i);
            vec2.push_back(n1 / i);
        }
    }
    // ベクトルをソートする
    sort(vec2.begin(), vec2.end());
    // すべての約数を出力する
    cout << "All the factors are -> ";
    for (int i = 0; i < vec2.size(); i++)
        cout << vec2[i] << " ";
    cout << endl;
    // 最大積を初期化(どの数も1で割り切れる)
    int maxProduct2 = 1;
    bool flag2 = 1;
    // 3重ループで3つの約数の組み合わせを探索する
    for (int i = 0; i < vec2.size(); i++) {
        for (int j = i; j < vec2.size(); j++) {
            for (int k = j; k < vec2.size(); k++) {
                // 4つ目の約数を y として求める
                int y = n1 - vec2[i] - vec2[j] - vec2[k];
                // 4つ目の約数が負になった場合はループを抜ける
                if (y <= 0)
                    break;
                // 前回より良い値があれば最大積を更新する
                if (n1 % y == 0) {
                    flag2 = 0;
                    maxProduct2 = max(vec2[i] * vec2[j] * vec2[k] * y, maxProduct2);
                }
            }
        }
    }
    // 条件を満たす組が存在すれば積を出力する
    if (flag2 == 0)
        cout << "Product is -> " << maxProduct2 << endl;
    else
        cout << "Not possible" << endl;
}

// ドライバーコード
int main(){
    int n1;
    n1 = 80;
    findfactors2(n1);
    return 0;
}

実行結果

All the factors are -> 1 2 4 5 8 10 16 20 40 80
Product is -> 160000

計算量とポイント

約数の列挙には O(√N) の計算時間がかかります。その後の3重ループによる組み合わせの探索は、約数の個数を d とすると O(d³) です。ここで重要なのは、4つ目の約数が「N − 選んだ3つの約数の合計」として自動的に決まるため、4重ループにする必要がない点です。これにより無駄な探索を省き、効率よく最大積を求められます。また、4つ目の候補 y が実際に N の約数であるかを「n % y == 0」で確認してから積を更新している点も、誤った答えを防ぐために欠かせません。