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

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

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

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

输入 18

输出:  9

解释: 

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

大数字" title="最大数字">最大数字总和为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

以上是 在C ++中找到n的所有因数的最大数字和 的全部内容, 来源链接: utcz.com/z/320065.html

回到顶部