# cathe how Algorithm to find Largest prime factor of a number

Here's the best algorithm I know of (in Python)

```
def prime_factors(n):
"""Returns all the prime factors of a positive integer"""
factors = []
d = 2
while n > 1:
while n % d == 0:
factors.append(d)
n /= d
d = d + 1
return factors
pfs = prime_factors(1000)
largest_prime_factor = max(pfs) # The largest element in the prime factor list
```

The above method runs in `O(n)`

in the worst case (when the input is a prime number).

**EDIT:**

Below is the `O(sqrt(n))`

version, as suggested in the comment. Here is the code, once more.

```
def prime_factors(n):
"""Returns all the prime factors of a positive integer"""
factors = []
d = 2
while n > 1:
while n % d == 0:
factors.append(d)
n /= d
d = d + 1
if d*d > n:
if n > 1: factors.append(n)
break
return factors
pfs = prime_factors(1000)
largest_prime_factor = max(pfs) # The largest element in the prime factor list
```

What is the best approach to calculating the largest prime factor of a number?

I'm thinking the most efficient would be the following:

- Find lowest prime number that divides cleanly
- Check if result of division is prime
- If not, find next lowest
- Go to 2.

I'm basing this assumption on it being easier to calculate the small prime factors. Is this about right? What other approaches should I look into?

Edit: I've now realised that my approach is futile if there are more than 2 prime factors in play, since step 2 fails when the result is a product of two other primes, therefore a recursive algorithm is needed.

Edit again: And now I've realised that this does still work, because the last found prime number has to be the highest one, therefore any further testing of the non-prime result from step 2 would result in a smaller prime.

All numbers can be expressed as the product of primes, eg:

```
102 = 2 x 3 x 17
712 = 2 x 2 x 2 x 89
```

You can find these by simply starting at 2 and simply continuing to divide until the result isn't a multiple of your number:

```
712 / 2 = 356 .. 356 / 2 = 178 .. 178 / 2 = 89 .. 89 / 89 = 1
```

using this method you don't have to actually calculate any primes: they'll all be primes, based on the fact that you've already factorised the number as much as possible with all preceding numbers.

```
number = 712;
currNum = number; // the value we'll actually be working with
for (currFactor in 2 .. number) {
while (currNum % currFactor == 0) {
// keep on dividing by this number until we can divide no more!
currNum = currNum / currFactor // reduce the currNum
}
if (currNum == 1) return currFactor; // once it hits 1, we're done.
}
```

JavaScript code:

```
'option strict';
function largestPrimeFactor(val, divisor = 2) {
let square = (val) => Math.pow(val, 2);
while ((val % divisor) != 0 && square(divisor) <= val) {
divisor++;
}
return square(divisor) <= val
? largestPrimeFactor(val / divisor, divisor)
: val;
}
```

Usage Example:

```
let result = largestPrimeFactor(600851475143);
```

The simplest solution is a pair of *mutually recursive* functions.

The first function generates all the prime numbers:

- Start with a list that consists of 2 and all odd numbers greater than 2.
- Remove all numbers that are not prime. That is, numbers that have no prime factors (other than themselves). See below.

The second function returns the prime factors of a given number `n`

in increasing order. The strategy is to try to divide `n`

by each prime that could possibly be its divisor:

- Take a list of all the primes in increasing order (see above).
- Let
`p`

be a prime in that list, and`ps`

be the prime factors of`n/p`

(see step 1).- If
`p`

squared is greater than our number`n`

, then`n`

is prime. We are done. - If
`p`

divides`n`

, then`p`

is a prime factor of`n`

. The other factors are`ps`

. - Otherwise
`p`

is not a prime factor of`n`

.

- If

The largest prime factor of `n`

is the last number given by the second function.

For clarification, here is the code for the above, in Haskell:

```
import Control.Monad
-- All the primes
primes = 2 : filter (ap (<=) (head . primeFactors)) [3,5..]
-- Gives the prime factors of its argument
primeFactors = factor primes
where factor [] n = []
factor xs@(p:ps) n =
if p*p > n then [n]
else let (d,r) = divMod n p in
if r == 0 then p : factor xs d
else factor ps n
-- Gives the largest prime factor of its argument
largestFactor = last . primeFactors
```

I'm aware this is not a fast solution. Posting as hopefully easier to understand slow solution.

```
public static long largestPrimeFactor(long n) {
// largest composite factor must be smaller than sqrt
long sqrt = (long)Math.ceil(Math.sqrt((double)n));
long largest = -1;
for(long i = 2; i <= sqrt; i++) {
if(n % i == 0) {
long test = largestPrimeFactor(n/i);
if(test > largest) {
largest = test;
}
}
}
if(largest != -1) {
return largest;
}
// number is prime
return n;
}
```

I am using algorithm which continues dividing the number by it's current Prime Factor.

My Solution in python 3 :

```
def PrimeFactor(n):
m = n
while n%2==0:
n = n//2
if n == 1: # check if only 2 is largest Prime Factor
return 2
i = 3
sqrt = int(m**(0.5)) # loop till square root of number
last = 0 # to store last prime Factor i.e. Largest Prime Factor
while i <= sqrt :
while n%i == 0:
n = n//i # reduce the number by dividing it by it's Prime Factor
last = i
i+=2
if n> last: # the remaining number(n) is also Factor of number
return n
else:
return last
print(PrimeFactor(int(input())))
```

Input : `10`

Output : `5`

Input : `600851475143`

Output : `6857`

```
#python implementation
import math
n = 600851475143
i = 2
factors=set([])
while i<math.sqrt(n):
while n%i==0:
n=n/i
factors.add(i)
i+=1
factors.add(n)
largest=max(factors)
print factors
print largest
```

Here is my approach to quickly calculate the largest prime factor.
It is based on fact that modified `x`

does not contain non-prime factors. To achieve that, we divide `x`

as soon as a factor is found. Then, the only thing left is to return the largest factor. It would be already prime.

The code (Haskell):

```
f max' x i | i > x = max'
| x `rem` i == 0 = f i (x `div` i) i -- Divide x by its factor
| otherwise = f max' x (i + 1) -- Check for the next possible factor
g x = f 2 x 2
```

Found this solution on the web by "James Wang"

```
public static int getLargestPrime( int number) {
if (number <= 1) return -1;
for (int i = number - 1; i > 1; i--) {
if (number % i == 0) {
number = i;
}
}
return number;
}
```

It seems to me that step #2 of the algorithm given isn't going to be all that efficient an approach. You have no reasonable expectation that it is prime.

Also, the previous answer suggesting the Sieve of Eratosthenes is utterly wrong. I just wrote two programs to factor 123456789. One was based on the Sieve, one was based on the following:

```
1) Test = 2
2) Current = Number to test
3) If Current Mod Test = 0 then
3a) Current = Current Div Test
3b) Largest = Test
3c) Goto 3.
4) Inc(Test)
5) If Current < Test goto 4
6) Return Largest
```

This version was 90x faster than the Sieve.

The thing is, on modern processors the type of operation matters far less than the number of operations, not to mention that the algorithm above can run in cache, the Sieve can't. The Sieve uses a lot of operations striking out all the composite numbers.

Note, also, that my dividing out factors as they are identified reduces the space that must be tested.

With Java:

For `int`

values:

```
public static int[] primeFactors(int value) {
int[] a = new int[31];
int i = 0, j;
int num = value;
while (num % 2 == 0) {
a[i++] = 2;
num /= 2;
}
j = 3;
while (j <= Math.sqrt(num) + 1) {
if (num % j == 0) {
a[i++] = j;
num /= j;
} else {
j += 2;
}
}
if (num > 1) {
a[i++] = num;
}
int[] b = Arrays.copyOf(a, i);
return b;
}
```

For `long`

values:

```
static long[] getFactors(long value) {
long[] a = new long[63];
int i = 0;
long num = value;
while (num % 2 == 0) {
a[i++] = 2;
num /= 2;
}
long j = 3;
while (j <= Math.sqrt(num) + 1) {
if (num % j == 0) {
a[i++] = j;
num /= j;
} else {
j += 2;
}
}
if (num > 1) {
a[i++] = num;
}
long[] b = Arrays.copyOf(a, i);
return b;
}
```

I think it would be good to store somewhere all possible primes smaller then n and just iterate through them to find the biggest divisior. You can get primes from prime-numbers.org.

Of course I assume that your number isn't too big :)

Here is the same function@Triptych provided as a generator, which has also been simplified slightly.

```
def primes(n):
d = 2
while (n > 1):
while (n%d==0):
yield d
n /= d
d += 1
```

the max prime can then be found using:

```
n= 373764623
max(primes(n))
```

and a list of factors found using:

```
list(primes(n))
```