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