파이썬으로 숫자의 고유한 소인수 곱 구하기 – 완전 탐색부터 효율적인 알고리즘까지

이 글에서는 다음 문제를 파이썬으로 해결하는 방법을 단계별로 살펴봅니다.

문제 정의

하나의 자연수 n이 주어졌을 때, n을 구성하는 모든 고유한(중복되지 않은) 소인수를 찾아 그 곱을 반환하는 프로그램을 작성해야 합니다.

예시

입력: num = 11
출력: 곱은 11

설명

입력값 11은 자기 자신 외에는 약수가 없는 소수이므로 소인수가 11 하나뿐입니다. 따라서 고유한 소인수들의 곱 역시 11이 됩니다.

반면 12처럼 여러 소인수를 가진 수(12 = 2 × 2 × 3)의 경우, 중복을 제거한 소인수는 2와 3이므로 곱은 2 × 3 = 6이 됩니다.

방법 1: 완전 탐색(Brute Force)

가장 직관적인 방법은 2부터 n까지 모든 수를 하나씩 확인하는 것입니다. 각 숫자 i에 대해 다음 두 조건을 검사합니다.

1. i가 n의 약수인지 (n % i == 0)
2. i 자체가 소수인지

두 조건을 모두 만족하면 i를 곱(product)에 누적하고, i가 n에 도달할 때까지 반복합니다.

예제 코드

def productPrimeFactors(n):
    product = 1
    for i in range(2, n + 1):
        if n % i == 0:              # i가 n의 약수인지 확인
            isPrime = 1
            for j in range(2, int(i ** 0.5) + 1):
                if i % j == 0:      # i가 소수가 아니면 표시
                    isPrime = 0
                    break
            if isPrime:             # i가 소수이면 곱에 누적
                product *= i
    return product

# 메인
n = 18
print(productPrimeFactors(n))

실행 결과

6

n = 18은 2 × 3 × 3으로 분해되므로 고유한 소인수는 2와 3이고, 곱은 2 × 3 = 6입니다.

이 방법은 구현이 간단하지만, 약수 여부와 소수 여부를 이중으로 검사하기 때문에 시간 복잡도가 O(n√n)에 가깝습니다. n이 커지면 실행 속도가 급격히 느려진다는 단점이 있습니다.

방법 2: 효율적인 소인수분해

소인수분해의 기본 원리를 활용하면 훨씬 빠르게 해결할 수 있습니다. 핵심 아이디어는 다음 세 단계로 정리됩니다.

1. 2 처리: n이 2로 나누어 떨어지는 동안 계속 2로 나눕니다. 이때 2는 곱에 한 번만 추가합니다.
2. 홀수 처리: 위 과정이 끝나면 n은 반드시 홀수가 됩니다. 이제 3부터 √n까지 홀수만 검사하면서(i는 2씩 증가), i가 n을 나눌 수 있는 동안 나누고 i를 곱에 한 번만 누적합니다.
3. 남은 소수 처리: 위 과정을 거친 후에도 n이 2보다 크다면, n 자체가 소수라는 의미이므로 n을 곱에 추가합니다.

예제 코드

import math

def productPrimeFactors(n):
    product = 1
    # 소인수 2 처리
    if n % 2 == 0:
        product *= 2
        while n % 2 == 0:
            n //= 2
    # 이 시점부터 n은 홀수
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        if n % i == 0:
            product *= i        # 소인수를 한 번만 곱함
            while n % i == 0:
                n //= i         # 같은 소인수는 모두 제거
    # 2보다 큰 소수가 남아 있다면 그 수 자체가 소인수
    if n > 2:
        product *= n
    return product

# 메인
n = 8
print(productPrimeFactors(n))

실행 결과

2

n = 8은 2 × 2 × 2로 분해되지만, 고유한 소인수는 2 하나뿐이므로 결과는 2입니다. 참고로 나눗셈 시 //(정수 나눗셈)를 사용하면 부동소수점 오류를 예방할 수 있습니다.

두 방법 비교

마무리

이 글에서는 주어진 수의 고유한 소인수들의 곱을 구하는 두 가지 접근 방식을 살펴보았습니다. 완전 탐색은 이해하기 쉽지만 느린 반면, 소인수분해 기반 방법은 O(√n)의 시간 복잡도로 큰 수에서도 빠르게 동작합니다. 실무에서는 입력 크기에 관계없이 안정적인 성능을 내는 후자의 알고리즘을 선택하는 것이 좋습니다.