在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