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