개요
이번 글에서는 주어진 숫자의 모든 짝수 소인수(짝수인 소수 인자)의 합을 효율적인 방법으로 구하는 방법을 살펴보겠습니다.
예를 들어 n = 480이라는 숫자가 있다고 가정해 봅시다. 480의 소인수는 2, 2, 2, 2, 2, 3, 5입니다. 이 중 짝수인 소인수는 2뿐이며, 총 다섯 번 등장하므로 짝수 소인수의 합은 2+2+2+2+2 = 10이 됩니다.
문제 해결 접근 방식
이 문제를 해결하려면 다음 규칙을 따르면 됩니다.
- 숫자가 2로 나누어 떨어지는 동안, 합계에 2를 더하고 숫자를 계속 2로 나눕니다.
- 이 과정이 끝나면 남은 숫자는 반드시 홀수입니다. 홀수에는 짝수인 소인수가 존재할 수 없으므로, 이후 등장하는 소인수들은 모두 무시하면 됩니다.
핵심 아이디어는 간단합니다. 2는 유일한 짝수 소수이기 때문에, 숫자에 포함된 2의 개수만 세면 곧 짝수 소인수의 개수가 되고, 이에 2를 곱한 값이 곧 원하는 합계입니다.
알고리즘
sumEvenFactors(n)
begin sum := 0 while n is divisible by 2, do sum := sum + 2 n := n / 2 done return sum end
C++ 코드 예제
#include<iostream>
using namespace std;
int sumEvenFactors(int n){
int sum = 0;
while(n % 2 == 0){
sum += 2;
n = n / 2; // n을 2로 나누어 줄여 나감
}
return sum;
}
int main() {
int n;
cout << "Enter a number: ";
cin >> n;
cout << "Sum of all even prime factors: " << sumEvenFactors(n);
return 0;
}실행 결과
Enter a number: 480 Sum of all even prime factors: 10
동작 설명
입력값이 480일 때 프로그램의 동작 과정은 다음과 같습니다.
- 480은 2로 나누어 떨어지므로 sum에 2를 더하고(합계: 2), 240이 됩니다.
- 240도 2로 나누어 떨어지므로 sum에 2를 더하고(합계: 4), 120이 됩니다.
- 같은 방식으로 60, 30, 15까지 반복되어 최종 합계는 10이 됩니다.
- 15는 홀수이므로 반복문이 종료되고, 결과값 10이 반환됩니다.
이 알고리즘은 2로 나누는 연산만 반복하므로 시간 복잡도는 O(log n)으로 매우 효율적입니다.