用 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

sudhir sharma

更新於： 27-Jan-2022

901 次瀏覽

開始您的 職業生涯

完成課程後，獲得認證

開始