#### 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=495Steppp^{2}n1 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*≤10^{12} 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 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.

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