在C ++中找到n的所有因数的最大数字和

在这个问题上，我们得到一个整数n。我们的任务是在n的所有除数中找到最大的数字总和。 

问题描述： 在这里，我们将找到数字n的除数，其数字总和最大。

让我们举个例子来了解这个问题， 

输入 18

输出：  9

解释： 

所有18的除数是1，2，3，6，9，18。

最大数字总和为9。

解决方法

找出数字N的所有除数。然后找到每个除数的位数之和，然后返回总和最大的值。

该程序说明了我们解决方案的工作原理，

示例

#include <iostream>
using namespace std;

int calcDigitSum(int n) {
   
   int sum = 0;
   while (n != 0) {
      sum = sum + n % 10;
      n = n/10;
   }
   return sum;
}

int largestDigitSumdivisior(int n) {
   
   int maxSum = 0;
   for (int i = 1; i <= n; i++)
      if (n % i == 0)
      maxSum = max(maxSum, calcDigitSum(i));

   return maxSum;
}

int main() {
   
   int n = 45;
   cout<<"数字总和最大的除数为 "<<largestDigitSumdivisior(n)<<endl;
   return 0;
}

输出结果

数字总和最大的除数为 9

通过修改方法以找到除数并使之更有效，可以使解决方案更有效。

在这个问题中，我们将迭代直到sqrt(n)找到所有除数，并且其他除数均使用n / div计算。这样可以减少找到的因数的时间复杂度sqrt(n)。 

该程序说明了我们解决方案的工作原理，

示例

#include <iostream>
using namespace std;

int calcDigitSum(int n) {
   
   int sum = 0;
   while (n != 0) {
      sum = sum + n % 10;
      n = n / 10;
   }
   return sum;
}

int largestDigitSumdivisior(int n) {
   
   int maxSum = 0;
   for (int i = 1; i*i <= n; i++) {

      if (n % i == 0) {
         maxSum = max(maxSum, calcDigitSum(i));
         maxSum = max(maxSum,calcDigitSum(n/i));
      }  
   }
   return maxSum;
}

int main() {
   
   int n = 32;
   cout<<"数字总和最大的除数为 "<<largestDigitSumdivisior(n)<<endl;
   return 0;
}

输出结果

数字总和最大的除数为 8