C/C++ 프로그램으로 숫자의 고유한 소인수 곱 구하기

이 글에서는 하나의 숫자가 가진 고유한 소인수(unique prime factors)들의 곱을 효율적으로 구하는 방법을 알아봅니다.

예를 들어 n = 1092라고 가정해 보겠습니다. 1092를 소인수분해하면 2 × 2 × 3 × 7 × 13이 됩니다. 여기서 중복을 제거한 고유한 소인수는 {2, 3, 7, 13}이며, 이들의 곱은 2 × 3 × 7 × 13 = 546입니다.

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

• 2 처리: 숫자가 2로 나누어 떨어지면 곱(prod)에 2를 곱한 뒤, 더 이상 나누어 떨어지지 않을 때까지 숫자를 2로 계속 나눕니다. 이렇게 하면 이후에 등장하는 중복된 2는 자동으로 무시됩니다.

• 홀수 인수 처리: 이 시점에서 숫자는 홀수입니다. 3부터 숫자의 제곱근까지 2씩 증가시키며(홀수만 검사) 탐색합니다. 현재 값 i로 나누어 떨어지면 i를 곱에 곱하고 숫자를 i로 나눈 후, 같은 방식으로 중복되는 i들을 제거합니다.

• 남은 수 처리: 마지막으로 남은 숫자가 2보다 크다면(즉, 1이 아니라면) 그 값 자체가 소인수이므로 곱에 곱해줍니다.

전체 흐름을 더 잘 이해하기 위해 알고리즘을 살펴보겠습니다.

알고리즘

uniquePrimeProduct(n)

시작
    prod := 1
    만약 n이 2로 나누어 떨어지면
        prod := prod * 2
        n := n / 2
    조건문 끝
    n이 2로 나누어 떨어지는 동안 반복
        n := n / 2
    반복 끝
    i := 3부터 √n까지, i는 2씩 증가하며 반복
        만약 n이 i로 나누어 떨어지면
            prod := prod * i
            n := n / i
        조건문 끝
        n이 i로 나누어 떨어지는 동안 반복
            n := n / i
        반복 끝
    반복 끝
    만약 n > 2이면
        prod := prod * n
    조건문 끝
끝

C 언어 구현 예제

#include<stdio.h>
#include<math.h>

int uniquePrimeProduct(int n){
    int i, prod = 1;
    if(n % 2 == 0){          // 2는 한 번만 곱함
        prod *= 2;
        n = n/2;
    }
    while(n % 2 == 0){       // 이후 중복되는 2는 건너뜀
        n = n/2;
    }
    for(i = 3; i <= sqrt(n); i=i+2){  // 홀수만 검사하기 위해 2씩 증가
        if(n % i == 0){
            prod *= i;
            n = n/i;
        }
        while(n % i == 0){   // 이후 중복되는 i는 건너뜀
            n = n/i;
        }
    }
    if(n > 2){               // 남은 수가 소인수인 경우
        prod *= n;
    }
    return prod;
}

int main() {
    int n;
    printf("숫자를 입력하세요: ");
    scanf("%d", &n);
    printf("고유한 소인수의 곱: %d", uniquePrimeProduct(n));
    return 0;
}

실행 결과

숫자를 입력하세요: 1092
고유한 소인수의 곱: 546

시간 복잡도

이 알고리즘은 3부터 √n까지의 홀수만 검사하므로 시간 복잡도는 O(√n)입니다. 가능한 모든 약수를 일일이 확인하는 완전 탐색 방식보다 훨씬 효율적이며, 비교적 큰 수에 대해서도 빠르게 동작합니다. 또한 각 소인수를 처음 발견했을 때만 곱에 반영하고 이후 중복분은 나누어 버리기 때문에, 별도의 집합 자료구조 없이도 고유한 소인수만 정확히 곱할 수 있다는 점이 핵심입니다.