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

Khái niệm

Cho số nguyên N, tìm tất cả ước số của N và in tích của bốn ước số sao cho:

• Tổng bốn ước số bằng N.
• Tích bốn ước số lớn nhất.

Nếu không tìm được 4 ước số như vậy, in "Không thể". Tất cả bốn ước số có thể bằng nhau để tối đa hóa tích.

Đầu vào

24

Đầu ra

Tất cả ước số -> 1 2 4 5 8 10 16 20 40 80 Tích -> 160000

Chọn ước số 20 bốn lần, 20+20+20+20 = 24, tích lớn nhất.

Phương pháp

Các bước:

• Tìm ước số của N bằng cách duyệt từ 1 đến sqrt(N), nếu i và n/i chia hết N thì lưu vào vector.
• Sắp xếp vector và in các ước số.
• Dùng ba vòng lặp lồng nhau tìm ba số để tối đa hóa tích với số thứ tư.
• Cập nhật tích lớn nhất.
• In tích khi tìm được bốn ước số.

Ví dụ

// C++ tìm bốn ước số của N với tích lớn nhất và tổng bằng N
#include <bits/stdc++.h>
using namespace std;

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 << "Tất cả ước số -> ";
    for (int i = 0; i < vec2.size(); i++)
        cout << vec2[i] << " ";
    cout << endl;
    int maxProduct2 = 1;
    bool flag2 = 1;
    for (int i = 0; i < vec2.size(); i++) {
        for (int j = i; j < vec2.size(); j++) {
            for (int k = j; k < vec2.size(); k++) {
                int y = n1 - vec2[i] - vec2[j] - vec2[k];
                if (y <= 0) break;
                if (n1 % y == 0) {
                    flag2 = 0;
                    maxProduct2 = max(vec2[i] * vec2[j] * vec2[k] * y, maxProduct2);
                }
            }
        }
    }
    if (flag2 == 0)
        cout << "Tích -> " << maxProduct2 << endl;
    else
        cout << "Không thể" << endl;
}

int main(){
    int n1 = 80;
    findfactors2(n1);
    return 0;
}

Đầu ra

Tất cả ước số -> 1 2 4 5 8 10 16 20 40 80 Tích -> 160000