Project Euler Problem 3

Solution

We want the largest prime factor of

$$600851475143$$

A standard approach is repeated trial division:

Start dividing by the smallest prime $2$.
Whenever a divisor $d$ divides $n$, divide $n$ by $d$ repeatedly.
Increase $d$ and continue until $d^2 > n$.
The remaining value of $n$ is then the largest prime factor.

This works because every composite factor has a smaller factor already tested.

Python code:

n = 600851475143
factor = 2
largest = 1

while factor * factor <= n:
    while n % factor == 0:
        largest = factor
        n //= factor
    factor += 1

if n > 1:
    largest = n

print(largest)

Tracing the factorization:

$$600851475143 = 71 \times 839 \times 1471 \times 6857$$

All of these are prime, so the largest prime factor is:

Answer: 6857