สมมติว่าเรามีจำนวนเต็ม N ภารกิจคือการหาตัวประกอบทั้งหมดของ N และแสดงผลคูณของปัจจัยสี่ตัวของ N นั้น -
-
ผลรวมของตัวประกอบทั้งสี่มีค่าเท่ากับ N
-
ผลคูณของปัจจัยสี่สูงสุด
สมมติว่าตัวเลขคือ 24 แล้วผลคูณคือ 1296 อย่างที่เราทราบตัวประกอบทั้งหมดคือ 1, 2, 3, 4, 6, 8, 12, 24 เราต้องเลือกตัวประกอบ 6 สี่ครั้ง ดังนั้น 6 + 6 + 6 + 6 =24 นี่คือผลคูณสูงสุด
ในการแก้ปัญหานี้ เราต้องหาตัวประกอบทั้งหมดตั้งแต่ 1 ถึง N จากนั้นเราต้องตรวจสอบเงื่อนไขเหล่านี้
-
หาก N เป็นจำนวนเฉพาะ คำตอบจะเป็นเท็จ
-
ถ้า n ที่กำหนดหารด้วย 4 ลงตัว คำตอบจะเป็น x^4 โดยที่ x คือผลหารเมื่อ n หารด้วย 4 ลงตัว
-
หากสามารถหาคำตอบได้ คำตอบจะต้องรวมปัจจัยสุดท้ายที่สามสองครั้ง จากนั้นเรียกใช้การวนซ้ำซ้อนสำหรับปัจจัยอีกสองประการ
ตัวอย่าง
#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 = 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
