Python에서 숫자의 가장 큰 소인수를 찾는 방법은 무엇입니까?

Python에서 소인수 찾기

수론의 일반적인 작업은 숫자의 소인수를 찾는 것입니다. 한 가지 가능한 방법은 단순히 숫자를 2부터 제곱근의 바닥까지 다른 모든 숫자로 나누고 나머지가 0인지 확인하는 것입니다. 그러나 이 접근 방식은 계산 비용이 많이 들 수 있습니다.

더 효율적인 무차별- 특히 숫자의 가장 큰 소인수를 찾기 위한 force 알고리즘은 아래에 나와 있습니다.

<code class="python">def largest_prime_factor(n):
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
    return n

이 알고리즘은 주어진 숫자의 제곱근까지 모든 숫자를 반복하여 작동합니다. 각 숫자에 대해 숫자가 주어진 숫자의 인수인지 확인하고 그렇다면 숫자를 인수로 나눕니다. 이 알고리즘은 숫자가 더 이상 범위의 숫자로 나누어지지 않고 나머지 숫자가 가장 큰 소인수가 될 때까지 계속됩니다.

<code class="python">largest_prime_factor(600851475143)
# Output: 6857

또는 숫자의 모든 소인수를 찾는 방법은 다음과 같습니다.

<code class="python">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</code>

위 내용은 Python에서 숫자의 가장 큰 소인수를 찾는 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!