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