使用 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

更新于： 30-Oct-2019

316 次浏览

开启你的 职业生涯

完成课程并获得认证

开始
广告