정수 N이 있다고 가정합니다. 작업은 N의 모든 인수를 찾고 N의 네 가지 인수의 곱을 표시하는 것입니다. 다음과 같이 -
-
네 가지 요소의 합은 N
-
4가지 요소의 곱이 최대입니다.
숫자가 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