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.

Actually there are several more efficient ways to find factors of big numbers (for smaller ones trial division works reasonably well).

One method which is very fast if the input number has two factors very close to its square root is known as Fermat factorisation. It makes use of the identity N = (a + b)(a - b) = a^2 - b^2 and is easy to understand and implement. Unfortunately it's not very fast in general.

The best known method for factoring numbers up to 100 digits long is the Quadratic sieve. As a bonus, part of the algorithm is easily done with parallel processing.

Yet another algorithm I've heard of is Pollard's Rho algorithm. It's not as efficient as the Quadratic Sieve in general but seems to be easier to implement.

Once you've decided on how to split a number into two factors, here is the fastest algorithm I can think of to find the largest prime factor of a number:

Create a priority queue which initially stores the number itself. Each iteration, you remove the highest number from the queue, and attempt to split it into two factors (not allowing 1 to be one of those factors, of course). If this step fails, the number is prime and you have your answer! Otherwise you add the two factors into the queue and repeat.

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

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.My answer is based on Triptych's, but improves a lot on it. It is based on the fact that beyond 2 and 3, all the prime numbers are of the form 6n-1 or 6n+1.

I recently wrote a blog article explaining how this algorithm works.

I would venture that a method in which there is no need for a test for primality (and no sieve construction) would run faster than one which does use those. If that is the case, this is probably the fastest algorithm here.

JavaScript code:

Usage Example:

Here is an example of the code:

Similar to @Triptych answer but also different. In this example list or dictionary is not used. Code is written in Ruby

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

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

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.

The simplest solution is a pair of

mutually recursivefunctions.The first function generates all the prime numbers:

The second function returns the prime factors of a given number

`n`

in increasing order.`n`

.The largest prime factor of

`n`

is the last number given by the second function.This algorithm requires a

lazy listor a language (or data structure) withcall-by-needsemantics.For clarification, here is one (inefficient) implementation of the above in Haskell:

Making this faster is just a matter of being more clever about detecting which numbers are prime and/or factors of

`n`

, but the algorithm stays the same.There are some modulo tests that are superflous, as n can never be divided by 6 if all factors 2 and 3 have been removed. You could only allow primes for i, which is shown in several other answers here.

You could actually intertwine the sieve of Eratosthenes here:

Also see this question.

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

Python Iterative approach by removing all prime factors from the number

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

My Solution in python 3 :

Input :

`10`

Output :`5`

Input :

`600851475143`

Output :`6857`

Here is my attempt in c#. The last print out is the largest prime factor of the number. I checked and it works.

Calculates the largest prime factor of a number using recursion in C++. The working of the code is explained below:

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):

The following C++ algorithm is not the best one, but it works for numbers under a billion and its pretty fast

Found this solution on the web by "James Wang"

Prime factor using sieve :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:

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.

Compute a list storing prime numbers first, e.g. 2 3 5 7 11 13 ...

Every time you prime factorize a number, use implementation by Triptych but iterating this list of prime numbers rather than natural integers.

With Java:

For

`int`

values:For

`long`

values:This is probably not always faster but more optimistic about that you find a big prime divisor:

`N`

is your number`return(N)`

`Sqrt(N)`

`N is divisible by Prime`

then`Return(Prime)`

Edit: In step 3 you can use the Sieve of Eratosthenes or Sieve of Atkins or whatever you like, but by itself the sieve won't find you the biggest prime factor. (Thats why I wouldn't choose SQLMenace's post as an official answer...)

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 :)

Not the quickest but it works!

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

the max prime can then be found using:

and a list of factors found using: