C 언어로 숫자의 홀수 소인수 합 효율적으로 구하기

개요

이 글에서는 주어진 숫자의 모든 홀수 소인수의 합을 효율적인 방법으로 구하는 프로그램을 C 언어로 작성해 보겠습니다.

예를 들어 n = 1092라고 가정해 봅시다. 이 숫자의 소인수는 2, 2, 3, 7, 13입니다. 여기서 홀수인 인수만 골라 더하면 3 + 7 + 13 = 23이 됩니다.

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

• 숫자가 2로 나누어떨어지면 해당 인수는 무시하고, 숫자를 2로 반복해서 나눕니다.
• 이 과정을 거치면 숫자는 반드시 홀수가 됩니다. 이제 3부터 숫자의 제곱근(√n)까지 탐색하면서, 현재 값으로 나누어떨어지면 그 값을 합에 더하고 숫자를 현재 값으로 나눈 뒤 계속 진행합니다.
• 마지막으로 남은 숫자가 홀수라면 그 값도 합에 더해 줍니다.

알고리즘을 통해 좀 더 자세히 살펴보겠습니다.

알고리즘

sumOddFactors(n)

begin
    sum := 0
    while n is divisible by 2, do
        n := n / 2
    done
    for i := 3 to √𝑛, increase i by 2, do
        while n is divisible by i, do
            sum := sum + i
            n := n / i
        done
    done
    if n > 2, then
        if n is odd, then
            sum := sum + n
        end if
    end if
end

C 언어 예제 코드

#include<stdio.h>
#include<math.h>
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;
}
main() {
    int n;
    printf("Enter a number: ");
    scanf("%d", &n);
    printf("Sum of all odd prime factors: %d", sumOddFactors(n));
}

실행 결과

Enter a number: 1092
Sum of all odd prime factors: 23

동작 원리 정리

이 알고리즘은 먼저 2로 나누어떨어지는 동안 계속 나누어 짝수 인수를 모두 제거합니다. 이후에는 3부터 시작해 2씩 증가시키며 홀수만 검사하기 때문에 불필요한 연산을 줄일 수 있습니다. 또한 약수를 확인할 때 제곱근까지만 검사하면 되므로 시간 복잡도는 대략 O(√n) 수준으로 매우 효율적입니다. 마지막에 남은 값이 2보다 큰 홀수라면 그 자체가 소인수이므로 합에 추가하면 됩니다.