Tìm 4 ước số của N tích lớn nhất và tổng bằng N trong C++

Cho số nguyên N. Tìm 4 ước số (có thể trùng) của N sao cho tổng bằng N và tích lớn nhất. Ví dụ N=24: các ước là 1,2,3,4,6,8,12,24. Chọn 6,6,6,6 cho tổng 24, tích 1296.

Quan sát toán học

• N nguyên tố → không có nghiệm
• N chia hết cho 4 → chọn x = N/4 bốn lần, tích = x⁴
• Trường hợp khác: dùng ước số thứ 3 từ cuối lặp 2 lần, tìm 2 ước còn lại bằng lặp lồng

Ví dụ minh họa

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool isPrime(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n%2==0 || n%3==0) return false;
    for (int i=5; i*i<=n; i+=6)
        if (n%i==0 || n%(i+2)==0) return false;
    return true;
}

void getFactors(int n, vector factors[]) {
    for (int i=2; i factors[n+1];
    getFactors(n+1, factors);
    
    if (n % 4 == 0) {
        int x = n/4;
        return x*x*x*x;
    }
    if (isPrime(n)) return -1;
    
    int ans = -1;
    if (factors[n].size() > 2) {
        int f = factors[n][factors[n].size()-3];
        for (int i = factors[n].size()-1; i >= 0; i--)
            for (int j = factors[n].size()-1; j >= 0; j--)
                if (2*f + factors[n][i] + factors[n][j] == n)
                    ans = max(ans, f*f*factors[n][i]*factors[n][j]);
    }
    return ans;
}

int main() {
    int n = 24;
    cout << "Tích lớn nhất: " << maxProduct(n);
    return 0;
}

Kết quả

Tích lớn nhất: 1296