在C ++中找到具有最大乘积和等于N的四个N因子

• Z时代
• 2024-01-10
• 分类：综合

假设我们有一个整数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

以上是 在C ++中找到具有最大乘积和等于N的四个N因子 的全部内容， 来源链接： utcz.com/z/327307.html