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 ?

Solution

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, …}.

Prime factors, p, are subtracted from n until the current prime factor’s square, p*p, exceeds the remaining value of n; this will be both the last and largest prime factor (since p is in ascending order).

Below is a walk-through 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
  else: 
    p += 2 if p>2 else 1   # after 2, consider only odd p

Example: n=495
Step  p       p2   n
  1   2  and  4 ≤ 495: 2 is not a factor of 495 so we increment p to 3 and try again.
  2   3  and  9 ≤ 495: 3 is a factor of 495: n = 165
  3   3  and  9 ≤ 165: and 3 is a factor of 165: n = 55
  4   3  and  9 ≤  55: but, 3 is not a factor of 55 so we increment p to 5 and try again.
  5   5  and 25 ≤  55: 5 is a factor of 55: n = 11
  6   5  and 25 >  11: the while loop terminates and 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.

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.

As a practical application of this algorithm see the Javascript prime factor calculator. It finds all the prime factors of a number.