Python에서 소인수를 찾기 위해 무차별 대입 알고리즘을 어떻게 최적화할 수 있습니까?

Python에서 소인수 찾기: 종합 가이드

소인수를 결정하는 것은 정수론의 기본 작업입니다. 가장 큰 소인수를 찾는 한 가지 접근 방식은 무차별 대입 알고리즘을 이용하는 것입니다. 그러나 모든 알고리즘이 동일하게 생성되는 것은 아닙니다.

무차별 대입 알고리즘

일반적으로 사용되는 알고리즘 중 하나는 원본과 균등하게 나누어지는 숫자를 찾을 때까지 숫자를 점진적으로 테스트하는 것입니다. 숫자. 예시 코드를 살펴보겠습니다.

n = 600851475143
i = 2
while i * i < n:
    while n % i == 0:
        n = n / i
    i = i + 1

print(n)

이 코드는 최대 소인수인 600851475143을 검색합니다. 그러나 완료하는 데 약 0.01초가 소요될 정도로 비효율적입니다.

최적화됨 무차별 대입 알고리즘

무차별 대입 알고리즘의 향상된 버전은 런타임을 크게 줄일 수 있습니다.

def largest_prime_factor(n):
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
    return n

이 알고리즘은 i가 n의 제곱근을 초과하자마자 종료됩니다. , 불필요한 숫자를 많이 테스트하는 것을 효과적으로 제거합니다. 결과적으로 실행 시간이 획기적으로 단축되어 동일한 입력에 대해 약 388마이크로초 만에 완료됩니다.

완전 소인수 분해

목표가 완전 소수를 얻는 것이라면 숫자를 인수분해하려면 알고리즘을 약간 수정해야 합니다.

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

이 알고리즘은 발견된 소인수를 저장하는 '인수'라는 목록을 유지합니다. n이 마지막에 1보다 크면 최종 소인수를 나타내며 목록에 추가됩니다.

결론적으로 효율적인 소인수분해 알고리즘을 선택하는 것이 성능에 매우 중요합니다. 최적화된 무차별 대입 알고리즘은 속도를 크게 향상시키는 반면, 완전 인수분해 알고리즘은 주어진 숫자의 전체 소인수분해를 제공합니다.

위 내용은 Python에서 소인수를 찾기 위해 무차별 대입 알고리즘을 어떻게 최적화할 수 있습니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!