Project Euler Problem 3 Solution

Project Euler & HackerRank Problem 3 Solution

Largest prime factor
by {BetaProjects} | MAY 17, 2009 | Project Euler & HackerRank

Project Euler Problem 3 Statement

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

What is the largest prime factor of the number 600851475143?

Solution

Clipart math tree

A reasonable way to solve this problem is to use trial division to factor an integer, n. In this instance, we create a set of possible integer factors, d, from the set {2} ∪ {3, 5, 7, 9, 11, …, √n} to try to divide n.

If any d does divide n then we remove all of those factors from n. What’s left is the remainder – the largest prime factor.

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

Finding the largest prime factor

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


Example: n = 6435
Step   d        d2    n
   1   2  and   4 ≤ 6435: 2 is not a factor of 6435, increment p to 3.
   2   3  and   9 ≤ 6435: 3 is a factor of 6435: n=n/3 = 2145
   3   3  and   9 ≤ 2145: and 3 is a factor of 2145: n=n/3 = 715
   4   3  and   9 ≤  715: but, 3 is not a factor of 715, increment p to 5.
   5   5  and  25 ≤  715: 5 is a factor of 715: n=n/5 = 143
   6   5  and  25 ≤  143: but, 5 is not a factor of 143, increment p to 7.
   7   7  and  49 ≤  143: but, 7 is not a factor of 143, increment p to 9.
   8   9  and  81 ≤  143: but, 9 is not a factor of 143, increment p to 11.1
   9  11  and 121 ≤  143: 11 is a factor of 143: n=n/11 = 13
  10  11  and 121 >   13: the while loop terminates and 13 is the largest prime factor.2
1Needless overhead to check 9 as all multiples of 3 have already been removed, but such is the cost for checking all odd numbers after 2 instead of building a list of prime numbers.
2The while’s conditional, d2 ≤ n, 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

HackerRank’s Project Euler Problem 3 runs up to 10 test cases with 10 ≤ N ≤ 1012

Python Source Code

download Python source code Use this link to download the Project Euler Problem 3: Largest prime factor.

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.

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