How to Find the Largest Prime Factor of a Number in Python?

Finding Prime Factors in Python

A common task in number theory is to find the prime factors of a number. One potential method is to simply divide the number by every other number from 2 to the floor of its square root, checking if the remainder is 0. However, this approach can be computationally expensive.

A more efficient brute-force algorithm specifically for finding the largest prime factor of a number is presented below:

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

This algorithm works by iterating through all numbers up to the square root of the given number. For each number, it checks if the number is a factor of the given number and divides the number by the factor if it is. The algorithm continues until the number is no longer divisible by any of the numbers in the range, and the remaining number is the largest prime factor.

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

Alternatively, for finding all the prime factors of a number:

<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>

The above is the detailed content of How to Find the Largest Prime Factor of a Number in Python?. For more information, please follow other related articles on the PHP Chinese website!