C++でNを除数で繰り返し除算した後の最大合計

この問題では、整数Nが与えられます。私たちのタスクは、C++でNを除数で繰り返し除算した後に最大の合計を見つけるプログラムを作成することです。

プログラムの説明 −数Nを1になるまで再帰的に除算してから、すべての約数を合計し、すべての約数の最大値を求めます。

問題を理解するために例を見てみましょう

入力 − n =12

出力 − 22

説明 −数値を再帰的に除算して、合計を求めましょう。

Division 1: 12/2 = 6
Division 2: 6/2 = 3
Division 3: 3/3 = 1
Sum = 12+6+3+1 = 22

この問題を解決するために、NをNの最小除数で割って個々の値を最大にすることにより、最大の合計を求めます。

例

ソリューションの動作を説明するプログラム

#include <bits/stdc++.h>
using namespace std;
int smallestDivisor(int n){
   int mx = sqrt(n);
   for (int i = 2; i <= mx; i++)
      if (n % i == 0)
         return i;
   return n;
}
int calculateMaxSum(int n) {
   long long maxSum = n;
   while (n > 1) {
      int divisor = smallestDivisor(n);
      n /= divisor;
      maxSum += n;
   }
   return maxSum;
}
int main(){
   int N = 12;
   cout<<"The maximum sum after repeatedly dividing "<<N<<" by divisor is "<<calculateMaxSum(N);
   return 0;
}

出力

The maximum sum after repeatedly dividing 12 by divisor is 22