在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<<"The divisor with largest sum of digits is "<<largestDigitSumdivisior(n)<<endl;
   return 0;
}

输出

The divisor with largest sum of digits is 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<<"The divisor with largest sum of digits is "<<largestDigitSumdivisior(n)<<endl;
   return 0;
}

输出

The divisor with largest sum of digits is 8

sudhir sharma

更新于：2021年1月25日

136 次浏览

开启您的职业生涯

完成课程获得认证

开始学习