C++로 숫자의 짝수 약수의 합을 구하는 방법

이 프로그램은 주어진 숫자의 모든 짝수 약수를 찾아 그 합을 계산한 뒤 결과를 출력하는 역할을 합니다.

문제 이해하기

예를 들어 다음과 같이 동작합니다.

입력 : 30
짝수 약수 : 2+6+10+30 = 48
출력 : 48

30의 약수 중 짝수인 값들은 2, 6, 10, 30이며, 이들을 모두 더하면 48이 됩니다.

해결 방법

가장 단순한 접근법은 숫자의 모든 약수를 찾은 후, 그중 짝수만 골라 합을 구하는 것입니다.

하지만 더 효율적인 방법은 소인수분해를 활용하는 것입니다. 소인수분해를 이용하면 약수의 합을 다음 공식으로 구할 수 있습니다.

약수의 총합 = (1 + d₁¹ + d₁² ... d₁^a1) × (1 + d₂¹ + d₂² ... d₂^a2) × ... × (1 + d_k¹ + d_k² ... d_k^ak)
여기서 di = 소인수, ai = 소인수 di의 지수

우리는 짝수 약수만 필요하므로, 주어진 수가 홀수라면 짝수 약수가 존재하지 않습니다. 따라서 이 경우에는 0을 출력하도록 처리합니다.

또한 짝수 약수의 합을 구할 때는 2의 지수 부분에서 1(2⁰)을 제외하고 계산해야 합니다. 2⁰ = 1은 홀수이기 때문입니다.

C++ 구현 예제

#include <iostream>
#include <math.h>
using namespace std;
int main() {
    int n=12;
    int m = n;
    if (n % 2 != 0)
       cout<<"The sum of all even factors of " << n <<" is "<<0;
    int evfac = 1;
    for (int i = 2; i <= sqrt(n); i++) {
       int count = 0, curr_sum = 1, curr_term = 1;
       while (n % i == 0) {
          count++;
          n = n / i;
          if (i == 2 && count == 1)
             curr_sum = 0;
          curr_term *= i;
          curr_sum += curr_term;
       }
       evfac *= curr_sum;
    }
    if (n >= 2)
       evfac *= (1 + n);
    cout <<"The sum of all even factors of " << m <<" is "<<evfac;
    return 0;
}

실행 결과

The sum of all even factors of 12 is 24

코드 설명

위 코드의 동작 과정을 살펴보면 다음과 같습니다.

1. 홀수 판별: 입력값 n이 홀수(n % 2 != 0)라면 짝수 약수가 하나도 없으므로 즉시 0을 출력합니다.

2. 소인수분해: 2부터 √n까지 반복하면서 각 소인수의 지수를 구합니다. 내부 while 루프에서 해당 인수로 나누어 떨어지는 동안 지수를 세고 누적합을 계산합니다.

3. 짝수 약수만 고려: 인수가 2이고 처음 등장했을 때(count == 1) curr_sum을 0으로 초기화하여 2⁰ = 1 항목을 제외합니다. 이렇게 하면 최종 곱에 홀수 성분이 포함되지 않습니다.

4. 남은 소인수 처리: √n보다 큰 소인수가 남아 있다면 (1 + n)을 곱해 마무리합니다.

예제에서 n = 12 = 2² × 3¹이므로, 짝수 약수의 합은 (2 + 4) × (1 + 3) = 6 × 4 = 24가 됩니다. 실제로 12의 짝수 약수는 2, 4, 6, 12이며 이들의 합도 24로 일치합니다.