หาตัวประกอบ 4 ตัวของ N ที่ผลคูณมากที่สุดและผลรวมเท่ากับ N ใน C++

แนวคิด

ได้รับจำนวนเต็ม N ให้หาตัวประกอบทั้งหมดของ N แล้วพิมพ์ผลคูณของตัวประกอบ 4 ตัวของ N ที่ทำให้:

• ผลรวมของตัวประกอบ 4 ตัวเท่ากับ N
• ผลคูณของตัวประกอบ 4 ตัวมากที่สุด

หากไม่สามารถหาตัวประกอบ 4 ตัวได้ ให้พิมพ์ "Not possible" หมายเหตุ: ตัวประกอบทั้ง 4 ตัวสามารถเท่ากันได้เพื่อให้ผลคูณมากที่สุด

อินพุต

24

เอาต์พุต

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

เลือกตัวประกอบ 20 4 ครั้ง,

ดังนั้น 20+20+20+20 = 24 และผลคูณสูงสุด

วิธีการ

ขั้นตอนอัลกอริทึมดังนี้:

• หาตัวประกอบของจำนวน 'N' โดยวนจาก 1 ถึงรากที่สองของ 'N' ตรวจสอบว่า 'i' และ 'n/i' หาร N ลงตัว เก็บในเวกเตอร์
• เรียงเวกเตอร์และพิมพ์ทุกสมาชิก
• หาตัวเลข 3 ตัวเพื่อเพิ่มผลคูณกับตัวที่ 4 โดยใช้ 3 ลูป
• แทนที่ผลคูณสูงสุดใหม่ด้วยผลคูณเก่า
• พิมพ์ผลคูณเมื่อหาตัวประกอบ 4 ตัวได้

ตัวอย่างโค้ด C++

// โปรแกรม C++ หาตัวประกอบ 4 ตัวของ N
// ที่ผลคูณมากที่สุดและผลรวมเท่ากับ N
#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 เป็นลบ ให้ break
                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