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

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} and try to divide n.

For all d that divide n, we remove d and all its factors. Once our set of factors are exhausted, the remainder becomes 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 = 6435
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 d 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 d 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 d to 7
  7   7  and  49 ≤  143: but, 7 is not a factor of 143, increment d to 9
  8   9  and  81 ≤  143: but, 9 is not a factor of 143, increment d to 111
  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 factor2
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 executing 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

Extended to solve all test cases for Project Euler Problem 3

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

Python Source Code

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

 Run Project Euler Problem 3 using Python on repl.it