Largest Prime Factor

The prime factors of $13195$ are $5, 7, 13$ and $29$.

What is the largest prime factor of the number $600851475143$?

Solution

Start with the smallest prime factor, $2$, and divide the number by it until it is no longer divisible. Then move on to the next candidate factor, $3$, and repeat. Continue until the number is $1$. Note that if a candidate is a factor, it must be prime, since any composite factor would have smaller prime factors that would have already been found.

Another level of optimization is to only check factors up to the square root of the number, since any factor larger than that would have a corresponding factor smaller than that, and we would have already found it.

def largest_prime_factor(number):
    i = 2
    while number > 1:
        if number % i == 0:
            number /= i
        elif i * i > number:
            i = number
        else:
            i += 1
    return int(i)

print(f"The largest prime factor of 600851475143 is {largest_prime_factor(600851475143)}")

The largest prime factor of 600851475143 is 6857