在 C++ 中查找 N 的四个因数，使其乘积最大且和等于 N - 集-2

概念

关于给定的整数 N，我们的任务是确定 N 的所有因数，并打印 N 的四个因数的乘积，使得 -

• 四个因数的和等于 N。
• 四个因数的乘积最大。

已经发现，如果不可能确定 4 个这样的因数，则打印“不可能”。需要注意的是，所有四个因数可以彼此相等以最大化乘积。

输入

N = 60

输出

All the factors are -> 1 2 3 4 5 6 10 12 15 20 30 60
Product is -> 50625

选择因子 15 四次，

因此，15+15+15+15 = 60 且乘积最大。

方法

这里解释了一种方法，该方法的复杂度为 O(P^3)，其中 P 是 N 的因数个数。

因此，借助以下步骤，可以获得时间复杂度为 O(N^2) 的有效方法。

• 我们将给定数字的所有因数存储在一个容器中。
• 现在我们迭代所有对并将它们的和存储在另一个容器中。
• 我们必须用 pair(element1, element2) 标记索引 (element1 + element2)，以便通过该和获得的元素。
• 我们再次迭代所有 pair_sums，并验证 n-pair_sum 是否存在于同一个容器中，因此这两对形成了四元组。
• 实现 pair 哈希数组以获得形成该对的元素。
• 最后，存储所有此类四元组中最大的一个，并在最后打印它。

示例

实时演示

// C++ program to find four factors of N
// with maximum product and sum equal to N
#include <bits/stdc++.h>
using namespace std;
// Shows function to find factors
// and to print those four factors
void findfactors1(int q){
   vector<int> vec1;
   // Now inserting all the factors in a vector s
   for (int i = 1; i * i <= q; i++) {
      if (q % i == 0) {
         vec1.push_back(i);
         vec1.push_back(q / i);
      }
   }
   // Used to sort the vector
   sort(vec1.begin(), vec1.end());
   // Used to print all the factors
   cout << "All the factors are -> ";
   for (int i = 0; i < vec1.size(); i++)
      cout << vec1[i] << " ";
      cout << endl;
      // So any elements is divisible by 1
      int maxProduct1 = 1;
      bool flag1 = 1;
      // implementing three loop we'll find
      // the three largest factors
      for (int i = 0; i < vec1.size(); i++) {
         for (int j = i; j < vec1.size(); j++) {
            for (int k = j; k < vec1.size(); k++) {
               // Now storing the fourth factor in y
               int y = q - vec1[i] - vec1[j] - vec1[k];
               // It has been seen that if the fouth factor become negative
               // then break
            if (y <= 0)
               break;
            // So we will replace more optimum number
            // than the previous one
            if (q % y == 0) {
               flag1 = 0;
               maxProduct1 = max(vec1[i] * vec1[j] * vec1[k] *y,maxProduct1);
            }
         }
      }
   }
   // Used to print the product if the numbers exist
   if (flag1 == 0)
      cout << "Product is -> " << maxProduct1 << endl;
   else
      cout << "Not possible" << endl;
}
// Driver code
int main(){
   int q;
   q = 60;
   findfactors1(q);
   return 0;
}

输出

All the factors are -> 1 2 3 4 5 6 10 12 15 20 30 60
Product is -> 50625

Arnab Chakraborty

更新于: 2020-07-24

71 次浏览

开启您的 职业生涯

通过完成课程获得认证

开始学习