파이썬으로 숫자의 고유한 소인수 곱 구하기

이 글에서는 아래 문제에 대한 해결 방법을 단계별로 살펴보겠습니다.

문제 정의

하나의 숫자 n이 주어졌을 때, n이 가진 서로 다른(고유한) 소인수들을 모두 찾아 그 곱을 반환하는 것이 목표입니다.

예시

입력: num = 11
출력: 곱은 11
설명:
입력 숫자 11은 소인수로 11 하나만 가지며,
따라서 곱도 11이 됩니다.

접근 방식 1: 브루트 포스

i = 2부터 n까지 반복하는 for 루프를 사용해 i가 n의 약수인지 확인하고, i 자체가 소수인지 검사합니다. 두 조건을 모두 만족하면 product 변수에 i를 곱해 저장하고, i가 n이 될 때까지 이 과정을 반복합니다.

예제 코드

def productPrimeFactors(n):
    product = 1
    for i in range(2, n + 1):
        if n % i == 0:
            isPrime = 1
            for j in range(2, int(i / 2) + 1):
                if i % j == 0:
                    isPrime = 0
                    break
            if isPrime:
                product = product * i
    return product

# main
n = 18
print(productPrimeFactors(n))

실행 결과

6

18의 고유한 소인수는 2와 3이며, 2 × 3 = 6이므로 결과는 6이 됩니다.

접근 방식 2: 효율적인 방법

브루트 포스 방식은 모든 수에 대해 소수 여부를 검사해야 하므로 비효율적일 수 있습니다. 대신 다음과 같이 개선할 수 있습니다.

• n이 2로 나누어 떨어지는 동안(짝수인 동안) 2를 곱에 포함하고 n을 2로 계속 나눕니다.
• 1단계가 끝나면 n은 반드시 홀수가 됩니다. 이제 i = 3부터 √n까지 2씩 증가시키며, i가 n을 나눌 수 있는 동안 i를 곱에 포함하고 n을 i로 나눕니다.
• 위 과정을 마친 후에도 n이 2보다 크다면 n 자체가 소수이므로 곱에 포함합니다.

예제 코드

import math

def productPrimeFactors(n):
    product = 1
    # 소인수 2 처리
    if n % 2 == 0:
        product *= 2
        while n % 2 == 0:
            n = n // 2
    # n은 이제 홀수
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        if n % i == 0:
            product = product * i
            while n % i == 0:
                n = n // i
    # n이 2보다 큰 소수인 경우
    if n > 2:
        product = product * n
    return product

# main()
n = 8
print(int(productPrimeFactors(n)))

실행 결과

2

8 = 2³이므로 고유한 소인수는 2뿐이고, 결과는 2가 됩니다. 이 방식은 약수를 √n까지만 검사하므로 시간 복잡도가 O(√n)으로 크게 줄어듭니다.

결론

이 글에서는 주어진 숫자의 고유한 소인수들의 곱을 구하는 두 가지 방법, 즉 단순 반복(브루트 포스) 방식과 제곱근을 활용한 효율적인 방식을 살펴보았습니다. 입력 값이 커질수록 O(√n)의 성능을 보이는 두 번째 방식이 훨씬 유리하므로, 실무에서는 효율적인 접근 방식을 사용하는 것을 권장합니다.