在 C++ 中找出 n 所有除数中数字的最大和
c++server side programmingprogramming
在这个问题中，我们给定一个整数 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
