### 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 = 6435Step d d^{2}n n%d==0(d divides n)?12 and 4 ≤ 6435 N: 2 is not a factor of 6435, incrementdto 323 and 9 ≤ 6435 Y: 3 is a factor of 6435:n=n//3= 214533 and 9 ≤ 2145 Y: 3 is a factor of 2145:n=n//3= 71543 and 9 ≤ 715 N: 3 is not a factor of 715, incrementdto 555 and 25 ≤ 715 Y: 5 is a factor of 715:n=n//5= 14365 and 25 ≤ 143 N: 5 is not a factor of 143, incrementdto 777 and 49 ≤ 143 N: 7 is not a factor of 143, incrementdto 989 and 81 ≤ 143 N: 9 is not a factor of 143, incrementdto 11911 and 121 ≤ 143 Y 11 is a factor of 143:n=n//11= 131011 and 121 > 13: thewhileloop terminates and 13 is the largest prime factor^{1}^{1}Thewhile’s conditional,d^{2}≤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

HackerRank runs up to 10 test cases with 10 ≤ *N* ≤ 10^{12}.

### Python Source Code

```
n = int(input('The largest prime factor of '))
while n%2==0: n//= 2 # Remove all even factors
d = 3
while d*d <= n:
if n % d == 0:
n//= d
else:
d+= 2
print ("is", 2 if n==1 else n)
```

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