C++를 활용해 숫자의 짝수 소인수 합 구하기

이 글에서는 주어진 숫자의 모든 짝수 소인수(짝수인 소수 인수)의 합을 효율적으로 구하는 방법을 알아보겠습니다. 예를 들어 n = 480이라는 숫자가 있다고 가정해 봅시다. 480의 소인수는 2, 2, 2, 2, 2, 3, 5입니다. 이 중 짝수인 소인수는 2뿐이며, 총 다섯 번 등장하므로 짝수 소인수의 합은 2+2+2+2+2 = 10이 됩니다.

이 문제를 해결하려면 다음 규칙만 기억하면 됩니다.

• 숫자가 2로 나누어 떨어지는 동안, 합계에 2를 더하고 숫자를 계속 2로 나눕니다.
• 이 과정이 끝나면 남은 숫자는 반드시 홀수입니다. 홀수에는 짝수인 약수가 존재할 수 없으므로, 나머지 인수들은 모두 무시해도 됩니다.

아래 알고리즘을 살펴보면 더 쉽게 이해할 수 있습니다.

알고리즘

printPrimeFactors(n):
begin
    sum := 0
    while n is divisible by 2, do
    sum := sum + 2
    n := n / 2
    done
end

예제 코드

#include<iostream>
using namespace std;
int sumEvenFactors(int n){
    int i, sum = 0;
    while(n % 2 == 0){
        sum += 2;
        n = n/2; // 2로 나누어 n 값을 줄임
    }
    return sum;
}
main() {
    int n;
    cout << "Enter a number: ";
    cin >> n;
    cout << "Sum of all even prime factors: "<< sumEvenFactors(n);
}

실행 결과

Enter a number: 480
Sum of all even prime factors: 10

핵심 포인트

2는 유일한 짝수 소수입니다. 따라서 어떤 수의 짝수 소인수는 오직 2 하나뿐이며, 그 합은 결국 '2가 곱해진 횟수 × 2'와 같습니다. 위 알고리즘은 n을 2로 계속 나누는 방식이기 때문에 시간 복잡도가 O(log₂ n)으로 매우 효율적이며, 큰 수에 대해서도 빠르게 동작합니다.