C++로 숫자의 홀수 소인수 합 구하기

이 글에서는 하나의 숫자에 대한 모든 홀수 소인수의 합을 효율적으로 구하는 방법을 살펴보겠습니다. 예를 들어 n = 1092라고 할 때, 이 수의 소인수는 2, 2, 3, 7, 13입니다. 이 중 홀수인 인수들만 골라 더하면 3 + 7 + 13 = 23이 됩니다.

이 문제를 해결하려면 다음과 같은 규칙을 따르면 됩니다.

• 숫자가 2로 나누어 떨어지면 해당 인수는 무시하고, 숫자가 더 이상 2로 나누어지지 않을 때까지 계속 2로 나눕니다.
• 이 시점에서 숫자는 반드시 홀수입니다. 3부터 숫자의 제곱근까지 2씩 증가시키며 반복하고, 현재 값으로 나누어 떨어지면 그 인수를 합에 더한 뒤 숫자를 현재 값으로 나누고 과정을 계속 진행합니다.
• 마지막으로 남은 숫자가 홀수라면, 그 값 역시 합에 더해줍니다.

좀 더 명확하게 이해할 수 있도록 알고리즘을 살펴보겠습니다.

알고리즘

sumOddFactors(n):
begin
   sum := 0
   while n이 2로 나누어 떨어지면 do
      n := n / 2
   done
   for i := 3부터 √n까지, i는 2씩 증가 do
      while n이 i로 나누어 떨어지면 do
         sum := sum + i
         n := n / i
      done
   done
   if n > 2 then
      if n이 홀수이면 then
         sum := sum + n
      end if
   end if
end

예제 코드

#include<iostream>
#include<cmath>
using namespace std;
int sumOddFactors(int n){
   int i, sum = 0;
   while(n % 2 == 0){
      n = n/2; // 2로 나누어 n을 줄여나감
   }
   // 더 이상 2로 나누어지지 않으므로, 남은 인수는 모두 홀수임
   for(i = 3; i <= sqrt(n); i=i+2){ // i를 2씩 증가시켜 홀수만 검사
      while(n % i == 0){
         sum += i;
         n = n/i;
      }
   }
   if(n > 2){
      if(n%2 == 1)
         sum += n;
   }
   return sum;
}
int main() {
   int n;
   cout << "숫자를 입력하세요: ";
   cin >> n;
   cout << "모든 홀수 소인수의 합: " << sumOddFactors(n);
}

실행 결과

숫자를 입력하세요: 1092
모든 홀수 소인수의 합: 23

이 방식은 먼저 2를 모두 제거한 뒤 홀수만 검사하기 때문에 불필요한 연산을 줄일 수 있습니다. 또한 약수는 제곱근까지만 확인해도 충분하므로 전체 시간 복잡도는 O(√n)이며, 이 덕분에 매우 큰 수에 대해서도 빠르게 동작합니다.