使用C ++查找最小数量因子。

在这里，我们将看到如何获得给定数量的因子的最小和。假设数字是12。我们可以通过不同的方式将其分解-

• 12 = 12 * 1（12 +1 = 13）

• 12 = 2 * 6（2 + 6 = 8）

• 12 = 3 * 4（3 + 4 = 7）

• 12 = 2 * 2 * 3（2 + 2 + 3 = 7）

最小和为7。我们将取一个数字，然后尝试找到最小因数和。为了获得最小因子之和，我们必须将因子尽可能长地分解。换句话说，我们可以说，如果我们尝试通过添加素数来找到总和S，那么总和将被最小化。

示例

#include<iostream>
using namespace std;
int primeFactorSum(int n) {
   int s = 0;
   for (int i = 2; i * i <= n; i++) {
      while (n % i == 0) {
         s += i;
         n /= i;
      }
   }
   s += n;
   return s;
}
int main() {
   int n = 12;
   cout << "Minimum sum of factors: " << primeFactorSum(n);
}

输出结果

Minimum sum of factors: 7