## 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

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 = 6435Stepdd^{2}n12 and 4 ≤ 6435: 2 is not a factor of 6435, increment`p`

to 3.23 and 9 ≤ 6435: 3 is a factor of 6435:`n=n/3`

= 214533 and 9 ≤ 2145: and 3 is a factor of 2145:`n=n/3`

= 71543 and 9 ≤ 715: but, 3 is not a factor of 715, increment`p`

to 5.55 and 25 ≤ 715: 5 is a factor of 715:`n=n/5`

= 14365 and 25 ≤ 143: but, 5 is not a factor of 143, increment`p`

to 7.77 and 49 ≤ 143: but, 7 is not a factor of 143, increment`p`

to 9.89 and 81 ≤ 143: but, 9 is not a factor of 143, increment`p`

to 11.^{1}911 and 121 ≤ 143: 11 is a factor of 143:`n=n/11`

= 131011 and 121 > 13: the`while`

loop terminates and`13`

is the largest prime factor.^{2}^{1}Needless 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.^{2}The`while`

’s conditional,d^{2}≤ 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* ≤ 10^{12}

### Python Source Code

### Last Word

Trial division, used here, works well for smaller numbers less than 10^{21}, 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.