C++로 자연수의 모든 약수에 대한 약수의 합 구하기

문제 개요

이 문제에서는 하나의 자연수 N이 주어집니다. 우리가 구해야 하는 값은 N의 모든 약수에 대해 각 약수의 약수 합을 계산한 뒤, 이를 모두 더한 총합입니다.

예시로 문제 이해하기

예제를 통해 문제를 자세히 살펴보겠습니다.

입력 : N = 12
출력 : 55

풀이 설명 −

12의 약수 : 1, 2, 3, 4, 6, 12
각 약수의 약수 합 = (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을 소인수분해하면 각 소인수와 지수를 알 수 있고, 이를 활용하면 모든 약수를 일일이 나열하지 않고도 수학적 공식으로 바로 정답을 계산할 수 있습니다.

N = p₁^a1 × p₂^a2 × ... × p_k^ak라고 할 때, 정답은 각 소인수 p와 그 지수 a에 대해 다음 식의 값을 구한 뒤 모두 곱한 값과 같습니다.

(a + 1) × 1 + a × p + (a − 1) × p² + ... + 1 × pᵃ

N = 12 = 2² × 3¹을 예로 들어 계산해 보면 다음과 같습니다.

• 소인수 2, 지수 2 → 3×1 + 2×2 + 1×4 = 11
• 소인수 3, 지수 1 → 2×1 + 1×3 = 5

두 값을 곱하면 11 × 5 = 55로, 앞서 약수를 직접 나열해 구한 결과와 일치합니다.

C++ 구현 예제

위 접근 방식을 C++로 구현한 프로그램입니다.

#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<<"모든 약수의 약수 합은 "<<findSumOfDivisorsOfDivisors(n);
   return 0;
}

실행 결과

모든 약수의 약수 합은 55

복잡도 분석

이 알고리즘은 소인수분해를 위해 2부터 √N까지만 확인하면 되므로 시간 복잡도는 O(√N)입니다. 모든 약수를 직접 나열하고 각 약수마다 다시 약수의 합을 구하는 완전탐색 방식보다 훨씬 빠르게 동작하며, N이 큰 경우에도 안정적인 성능을 보여줍니다.