Python으로 주어진 숫자의 모든 소인수 출력하기 – 효율적인 알고리즘 완벽 가이드

이 글에서는 아래의 문제 상황에 대한 해결 방법을 알아보겠습니다.

문제 정의

하나의 숫자 n이 주어졌을 때, 이 숫자의 모든 소인수(prime factor)를 찾아 출력하는 것이 목표입니다. 예를 들어 200이 입력되면 200 = 2 × 2 × 2 × 5 × 5이므로 2, 2, 2, 5, 5를 차례로 출력해야 합니다.

효율적인 접근 방법

2부터 n까지 모든 수를 일일이 나누어 보는 비효율적인 방식 대신, 다음 세 단계로 최적화하면 시간 복잡도를 O(√n)까지 줄일 수 있습니다.

1. 2로 반복해서 나누기: n이 짝수인 동안 계속 2로 나누며 2를 출력합니다. 이 과정이 끝나면 n은 반드시 홀수가 됩니다.
2. 홀수 인수 검사: 3부터 √n까지 홀수만 검사합니다. 각 i에 대해 i가 n을 나눌 수 있는 동안 계속 나누면서 i를 출력합니다.
3. 남은 소수 처리: 위 과정이 끝난 뒤 n이 2보다 크다면, 그 값 자체가 소수이므로 그대로 출력합니다.

예제 코드

# Python program to print prime factors
import math

def primeFactors(n):
    # n이 짝수인 동안 2로 나누기
    while n % 2 == 0:
        print(2)
        n = n // 2
    # n이 홀수가 되면 3부터 sqrt(n)까지 홀수만 검사
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        # i가 n을 나눌 수 있는 동안 반복
        while n % i == 0:
            print(i)
            n = n // i
    # 남은 n이 소수인 경우 출력
    if n > 2:
        print(n)

n = 200
primeFactors(n)

실행 결과

2
2
2
5
5

모든 변수와 함수는 전역 범위(global scope)에서 선언되어 있으므로, 프로그램 내 어디에서든 자유롭게 접근할 수 있습니다.

마무리

이 글에서는 2를 먼저 분리한 뒤 제곱근까지만 검사하는 최적화 기법을 활용하여, 주어진 숫자의 모든 소인수를 효율적으로 찾아 출력하는 Python 프로그램을 작성하는 방법을 배웠습니다. 이러한 접근 방식은 불필요한 연산을 크게 줄여주기 때문에, 큰 수를 다룰 때에도 빠른 성능을 보장한다는 점이 핵심 장점입니다.