Project Euler 3 Problem Statement

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

What is the largest prime factor of the number 600851475143 ?


This problem is solved without using arrays or a giant list of prime numbers. Instead, we generate prospective prime numbers, p, through trial division. The list of candidates for p are {2} and the set of odd natural numbers {3, 5, 7, 9, 11, 13, 15, …}.

All the prime factors, p, are removed from n until the current prime factor’s square, p*p, exceeds the residual value of n. The residual value of n is the largest prime factor.

Below is a walkthrough of this algorithm to show the process of removing prime factors and leaving the remainder as the largest prime factor of n.

Finding the largest prime factor

p = 2
while (p*p <= n):      
  if (n % p == 0): 
    n //= p
    p += 2 if p>2 else 1   # after 2, consider only odd p

Example: n=495
 p       p2   n
 2  and  4 ≤ 495: 2 is not a factor so its skipped and p is incremented to 3
 3  and  9 ≤ 495: 3 is a factor of 495: n = 165
 3  and  9 ≤ 165: 3 is a factor of 165: n = 55
 3  and  9 ≤  55: 3 is not a factor so its skipped and p is incremented to 5
 5  and 25 ≤  55: 5 is a factor of 55: n = 11
 5  and 25 ≤  55: 5 is not a factor so its skipped and p is incremented to 7
 7  and 49 ≤  55: 7 is not a factor so its skipped and p is incremented to 9
 9  and 81 not ≤ 55: the while loop terminates and n=11 is the largest prime factor.
The conditional of the while loop is checked after the loop's last statement.

If the given number, n, is already prime then n is returned as the largest prime factor, which is nice, because it is, in fact, itself the largest prime factor. As a practical application of this algorithm see the Javascript prime factor calculator. It finds all the prime factors of a number.

HackerRank version

The HackerRank version increases the limit for n≤1012 and runs 10 consecutive test cases. This algorithm handles those test cases without change.

Python 2.7 Source

Last Word

Trial division, used here, works well for smaller numbers less than 1021, for larger numbers there are several efficient algorithms available.

A more favorable method for factoring numbers under 100 digits long is the Quadratic sieve, a recent invention. It is a much simpler algorithm to implement compared to others and lends itself to parallelization. Because it is a sieve, large amounts of memory may be required.

Another is Pollard's Rho algorithm with improvements by Brent. It’s easy to program and fast for numbers with small factors.

Here are some examples using the calculator:
n = 600851475143, iterations:738
n = 600851475143600851475143, iterations:5006, largest prime factor: 99990001, <1 sec
n = 600856008514751431475143, iterations:11859442, largest prime factor: 562585074706409, <6 sec