Python에서 소인수를 찾는 방법

Python에서 정수의 소인수를 찾으려면 해당 정수를 소수로 반복해서 나누세요. 이 문서에서는 사용자 지정 시행 나눗셈 함수, 에라토스테네스의 체 접근법, 그리고 타사 primefac 패키지를 소개합니다. 인수는 반복되는 인수를 포함해 리스트로 반환됩니다.

소인수 분해 개요

정수의 인수는 그 정수를 나머지가 남지 않게 나눕니다. 소수는 1보다 크고 양의 인수가 정확히 두 개, 즉 1과 그 수 자체뿐인 수입니다. 예를 들어 3, 7, 11, 13은 소수입니다.

소인수 분해는 1보다 큰 정수를 소수들의 곱으로 나타냅니다. 6 = 2 × 3이므로 그 소인수는 2와 3입니다. 인수는 한 번 이상 나타날 수도 있습니다. 20 = 2 × 2 × 5이므로 그 소인수는 [2, 2, 5]입니다.

Python에서 소인수를 찾는 여러 접근법

작고 직접적인 구현에는 시행 나눗셈을 선택하고, 어떤 한도까지의 소수도 필요하면 체를 사용하며, 패키지가 소인수 분해를 제공하기를 원하면 primefac을 사용하세요. 아래 사용자 지정 함수는 각 소인수를 그 중복도와 함께 반환합니다.

소인수 분해를 수행하는 사용자 지정 함수

시행 나눗셈은 후보 약수를 오름차순으로 검사합니다. 후보가 남은 값을 나누어떨어지게 하면, 함수는 그 값을 기록하고 나누어 낸 다음 다시 검사합니다. 후보의 제곱이 남은 값보다 크지 않을 동안만 검사하면 충분합니다. 더 큰 인수가 남아 있다면 그 짝이 되는 인수는 이미 발견되었을 것이기 때문입니다. 1보다 큰 남은 값은 모두 소수입니다.

정수 20으로 이 예제를 실행하세요.

def prime_factors(n):
    if n < 1:
        return None

    factors = []
    divisor = 2
    while divisor * divisor <= n:
        if n % divisor == 0:
            factors.append(divisor)
            n //= divisor
        else:
            divisor += 1
    if n > 1:
        factors.append(n)
    return factors


print(prime_factors(20))

[2, 2, 5]

이 함수는 나누는 수 루프를 하나만 사용합니다. 먼저 소수 목록을 생성하지 않습니다. 그 // 연산은 남은 값을 정수로 유지합니다. None 결과는 1보다 작은 지원되지 않는 값을 나타냅니다. prime_factors(1)은 1에 소인수가 없으므로 []를 반환합니다.

에라토스테네스의 체를 사용해 소인수 분해 수행하기

에라토스테네스의 체는 각 소수의 배수를 그 소수의 제곱부터 표시해 나감으로써 어떤 한도까지의 모든 소수를 찾습니다. 하나의 정수를 인수분해하려면 그 정수까지만 체를 구축한 다음, 나열된 각 소수로 가능한 한 여러 번 나누어 내세요. 이 접근법은 소수 목록을 재사용할 경우에 유용합니다. 하나의 값을 인수분해하기 위해서만 체를 구축하면 불필요한 작업이 생길 수 있습니다. 아래 체는 그 한도를 포함해 그 한도까지의 소수를 반환합니다. 출력이 표시되지 않는 구문 및 알고리즘 예제입니다.

def primes_up_to(limit):
    if limit < 2:
        return []

    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False
    candidate = 2
    while candidate * candidate <= limit:
        if is_prime[candidate]:
            for multiple in range(candidate * candidate, limit + 1, candidate):
                is_prime[multiple] = False
        candidate += 1
    return [number for number, prime in enumerate(is_prime) if prime]


def factor_with_sieve(number):
    if number < 1:
        return None
    factors = []
    for prime in primes_up_to(number):
        while number % prime == 0:
            factors.append(prime)
            number //= prime
    return factors

에라토스테네스의 체에 대한 자세한 내용은 관련 가이드를 참조하세요. 사용자 지정 함수와 마찬가지로 이 버전은 1에 대해 []를, 1보다 작은 값에 대해 None을 반환합니다.

primefac 모듈을 사용해 소인수 분해 수행하기

primefac은 외부 Python 패키지이므로 프로그램을 실행하는 환경에 설치되어 있어야 합니다. 그 primefac() 함수는 소인수를 생성합니다. 결과를 표시하거나 시퀀스로 저장해야 할 경우 리스트로 변환하세요: list(primefac.primefac(20)). 이 선택지는 인수분해 로직을 사용자 지정 함수가 아닌 패키지에 둡니다. 패키지 호출은 인라인으로 표시됩니다. 이 문서의 자체 완결형 예제에는 해당 외부 종속성이 포함되어 있지 않고 설치하지도 않기 때문입니다.