数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究在C++中查找N的四个因数，使其乘积最大且和等于N
假设我们有一个整数N。任务是找到N的所有因数，并显示N的四个因数的乘积，使得：
四个因数的和等于N
四个因数的乘积最大
假设数字是24，则乘积是1296。我们知道所有因数是1、2、3、4、6、8、12、24。我们必须选择四个6。所以6 + 6 + 6 + 6 = 24。这里的乘积最大。
要解决这个问题，我们必须找到从1到N的所有因数，然后检查这些条件
如果N是素数，则答案为false
如果给定的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
更新于：2020年1月3日
93次浏览
广告