파이썬으로 숫자의 가장 큰 소인수 찾기

이 글에서는 주어진 양의 정수 n에 대해 그 수의 가장 큰 소인수(약수 중 가장 큰 소수)를 구하는 방법을 알아보겠습니다.

문제 정의

양의 정수 n이 하나 주어집니다. 우리가 해야 할 일은 이 수를 소인수분해했을 때 나오는 소수들 중 가장 큰 값을 찾는 것입니다.

예를 들어 n = 15라면, 15의 소인수는 3과 5이므로 가장 큰 소인수는 5입니다.

접근 방법

• 주어진 수를 작은 약수부터 차례대로 나누어 소인수분해를 진행합니다.
• 나누는 과정에서 발견되는 소인수 중 가장 큰 값을 계속 갱신해 나갑니다.
• 효율성을 높이기 위해 먼저 2로 나누어 떨어지는 만큼 처리한 뒤, 3부터 √n까지 홀수만 검사합니다.
• 마지막으로 2보다 큰 값이 남아 있다면, 그 값 자체가 곧 가장 큰 소인수입니다.

예제 코드

import math

def maxPrimeFactor(n):
    # 수가 짝수인 경우 2로 계속 나눈다
    while n % 2 == 0:
        max_Prime = 2
        n = n / 2
    # 남은 수가 홀수인 경우 3부터 √n까지 검사한다
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        while n % i == 0:
            max_Prime = i
            n = n / i
    # 2보다 큰 소수가 남아 있는 경우
    if n > 2:
        max_Prime = n
    return int(max_Prime)

# 위 함수를 테스트하기 위한 드라이버 코드
n = 15
print(maxPrimeFactor(n))

출력 결과

5

n = 15를 입력하면 소인수 3과 5 중 더 큰 값인 5가 출력됩니다.

복잡도 분석

• 시간 복잡도: O(√n) — 제곱근까지만 검사하므로 매우 효율적입니다.
• 보조 공간 복잡도: O(1) — 추가적인 메모리를 거의 사용하지 않습니다.

동작 원리

이 알고리즘의 핵심은 작은 소수부터 차례대로 나누어 제거하는 것입니다. 어떤 수 i가 n을 나누어 떨어지게 한다면, i가 합성수라면 이미 그보다 작은 소인수들이 먼저 제거되었을 것이므로 i는 반드시 소수입니다. 따라서 별도의 소수 판별 과정 없이도 올바른 소인수만 추출할 수 있습니다.

또한 √n까지만 검사해도 충분한 이유는, n의 약수 쌍 중 하나는 반드시 √n 이하이기 때문입니다. √n까지 나누고도 2보다 큰 값이 남았다면, 그 값은 √n보다 큰 유일한 소인수, 즉 가장 큰 소인수임이 보장됩니다.

결론

이 글에서는 파이썬을 활용하여 주어진 수의 가장 큰 소인수를 찾는 방법을 살펴보았습니다. 2를 먼저 처리하고 홀수만 √n까지 검사하는 방식으로 시간 복잡도를 O(√n)까지 줄일 수 있으며, 추가 메모리 없이 동작하는 효율적인 알고리즘입니다. 이 기법은 암호학이나 수론 관련 문제에서 자주 활용되므로 잘 익혀두면 유용합니다.