Project Euler #3: Largest Prime Factor

Problem

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

Key Observation

If $p$ is the smallest prime factor of $n$, then $p \leq \sqrt{n}$. So we only need to trial-divide up to $\sqrt{n}$. After removing all such small factors, whatever remains is the largest prime factor.

For $n = 600851475143$, we have $\lfloor \sqrt{n} \rfloor = 775146$, so we need to check at most ~387,000 odd numbers — trivial for a computer.

Algorithm

The standard approach is trial division with factor stripping:

1. For each candidate $p = 2, 3, 5, 7, \ldots$, while $p^2 \leq n$:
   • While $p \mid n$: divide $n$ by $p$, record $p$ as the last factor.
   • Increment $p$.
2. If $n > 1$ after the loop, $n$ itself is prime and is the answer.

def largest_prime_factor(n: int) -> int:
    largest = 1
    # Factor out 2
    while n % 2 == 0:
        largest = 2
        n //= 2
    # Factor out odd primes
    p = 3
    while p * p <= n:
        while n % p == 0:
            largest = p
            n //= p
        p += 2
    # Remaining factor
    if n > 1:
        largest = n
    return largest

print(largest_prime_factor(600851475143))  # 6857

Why This Works

After stripping factor $p$ completely from $n$, the remaining $n$ has no factor $\leq p$. Its smallest prime factor is therefore $> p$. So when we check $p^2 > n$, the remaining $n$ must be prime (it has no factors in $[2, \sqrt{n}]$).

Formally: At each step, $n = \prod_{q > p} q^{e_q}$, where all $q$ are prime. Once $p > \sqrt{n}$, we have at most one such prime $q$, so $n$ is prime.

Factorization

The largest prime factor is $\boxed{6857}$.

Complexity

The algorithm runs in $O(\sqrt{n})$ time in the worst case (when $n$ is prime). For our input, $\sqrt{n} \approx 7.7 \times 10^5$, so it terminates almost instantly.

For very large $n$ (say $10^{20}$), one would use Pollard’s rho algorithm ($O(n^{1/4})$) or a quadratic sieve. But for Project Euler problems, trial division is almost always sufficient.