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