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

โจทย์

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

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

ตัวอย่าง: N = 24 ผลคูณคือ 1296 ตัวประกอบของ 24 คือ 1, 2, 3, 4, 6, 8, 12, 24 เลือกตัวประกอบ 6 จำนวน 4 ครั้ง (6+6+6+6=24) ให้ผลคูณสูงสุด

วิธีแก้ปัญหา

1. หาตัวประกอบทั้งหมดตั้งแต่ 1 ถึง N
2. ตรวจสอบเงื่อนไขดังนี้:
   • ถ้า N เป็นจำนวนเฉพาะ → ไม่มีคำตอบ
   • ถ้า N หาร 4 ลงตัว → คำตอบคือ x⁴ โดย x = N/4
   • กรณีอื่น ให้เลือกตัวประกอบลำดับที่ 3 จากท้าย สองครั้ง แล้ววนลูปหาตัวประกอบอีกสองตัวที่เหลือ

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

#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 get_factors(int N, vector<int> fact_vectors[]) {
    for (int i = 2; i < N; i++) {
        for (int j = 1; j * j <= i; j++) {
            if (i % j == 0) {
                if (i / j == j)
                    fact_vectors[i].push_back(j);
                else {
                    fact_vectors[i].push_back(j);
                    fact_vectors[i].push_back(i / j);
                }
            }
        }
        sort(fact_vectors[i].begin(), fact_vectors[i].end());
    }
}

int getProduct(int n) {
    vector<int> v[n + 100];
    get_factors(n + 100, v);
    if (n % 4 == 0) {
        int x = n / 4;
        x *= x;
        return x * x;
    } else {
        if (isPrime(n)) return -1;
        else {
            int ans = -1;
            if (v[n].size() > 2) {
                int fac = v[n][v[n].size() - 3];
                for (int i = v[n].size() - 1; i >= 0; i--) {
                    for (int j = v[n].size() - 1; j >= 0; j--) {
                        if ((fac * 2) + (v[n][j] + v[n][i]) == n)
                            ans = max(ans, fac * fac * v[n][j] * v[n][i]);
                    }
                }
            }
            return ans;
        }
    }
}

int main() {
    int n = 24;
    cout << "The product is: " << getProduct(n);
}

ผลลัพธ์

The product is: 1296