用 C++ 找出某个自然数的所有除数的除数之和

在这个问题中，我们得到一个自然数 N。我们的任务是求某个自然数所有除数的除数之和。

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

Input : N = 12
Output : 55

解释 −

The divisors of 12 are 1, 2, 3, 4, 6, 12
Sum of divisors = (1) + (1 + 2) + (1 + 3) + (1 + 2 + 4) + (1 + 2 + 3 + 6) + (1 + 2 + 3 + 4 + 6 + 12) = 1 + 3 + 4 + 7 + 12 + 28 = 55

解决方法

解决此问题的简单方法是利用 N 的分母。利用质因数分解，我们可以求出所有除数的除数之和。这里，我们将找出每个元素的质因数分解。

示例

程序展示我们解决方案的工作原理

#include<bits/stdc++.h>
using namespace std;
int findSumOfDivisorsOfDivisors(int n) {
   map<int, int> factorCount;
   for (int j=2; j<=sqrt(n); j++) {
      int count = 0;
      while (n%j == 0) {
         n /= j;
         count++;
      }
      if (count) 
         factorCount[j] = count;
   }
   if (n != 1)
      factorCount[n] = 1;
   int sumOfDiv = 1;
   for (auto it : factorCount) {
      int power = 1; 
      int sum = 0;
      for (int i=it.second+1; i>=1; i--) {
         sum += (i*power);
         power *= it.first;
      }
      sumOfDiv *= sum;
   }
   return sumOfDiv;
}
int main() {
   int n = 12;
   cout<<"The sum of divisors of all divisors is "<<findSumOfDivisorsOfDivisors(n);
   return 0;
}

输出

The sum of divisors of all divisors is 55

更新于： 27-Jan-2022

901 次浏览

开始您的 职业生涯

完成课程后，获得认证

开始
广告