1930

12
+3  Q:

## Prime factors

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

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

1. Find lowest prime number that divides cleanly
2. Check if result of division is prime
3. If not, find next lowest
4. 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.

A:

Take a look at the Sieve of Eratosthenes

The Sieve of Eratosthenese is effective for generating all primes up to a certain number.It is not for finding the largest prime factor of a number. This answer should not be accepted.
See my answer--the Sieve is *SLOW* for this purpose.
agreed - clearly artelius has the correct answer
A:

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

A:

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

1. `N` is your number
2. If it is prime then `return(N)`
3. Calculate primes up until `Sqrt(N)`
4. Go through the primes in descending order (largest first)
• If `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...)

A:

Not the quickest but it works!

``````    static bool IsPrime(long num)
{
long checkUpTo = (long)Math.Ceiling(Math.Sqrt(num));
for (long i = 2; i <= checkUpTo; i++)
{
if (num % i == 0)
return false;
}
return true;
}
``````
This is not an answer to the question. ;-) The question was about finding the largest prime factor, not checking for primality.
-1, since not prime factors are searched with this code
It is much more efficient to initialise your loop as (long i = 3; i < checkUpTo; i+= 2)
A:
``````n = abs(number);
result = 1;
if (n mod 2 == 0) {
result = 2;
while (n mod 2 = 0) n /= 2;
}
for(i=3; i<sqrt(n); i+=2) {
if (n mod i == 0) {
result = i;
while (n mod i = 0)  n /= i;
}
}
return max(n,result)
``````

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:

• First create the list of integers up to sqrt(n).
• In the for loop mark all multiples of i up to the new sqrt(n) as not prime, and use a while loop instead.
• set i to the next prime number in the list.

Also see this question.

+15  A:

Actually there are several more efficent ways to find factors of numbers. 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.

Note - I know the links are retarded. This seems to be a stackoverflow bug. If anyone can find a workaround that would help.
workaround is to escape the single quote or use <a href="http://foo.com">foo</a> link syntax
ps which lemming type are you? blocker, builder, digger.. :)
Bridge builder, I suppose...
A:

The simplest solution is a pair of mutually recursive functions.

The first function returns all the prime numbers.

1. Start with a list that consists of 2 and all odd numbers greater than 2.
2. Remove all numbers that have more than one prime factor (see below), as these numbers are not prime.

The second function returns the prime factors of a given number n, as follows:

1. Let p equal the first prime number (2).
2. Take a list of all the primes, starting with p (see above).
3. If p squared is greater than our number n, then n is prime and therefore its largest and only prime factor is itself. If p divides n, then p is a prime factor of n. The other factors are the prime factors of n divided by p. Go to 2. Otherwise, let p equal the next prime number and go back to step 2.

The largest prime factor of n is the last number given by the second function.

A:

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.
}
``````
Yes, but this is horribly inefficient. Once you've divided out all the 2s, you really shouldn't try dividing by 4, or by 6, or ...; It really is much more efficient in the limit to only check primes, or use some toher algorithm.
+1 to offset wnoise, who I think is wrong. Trying to divide by 4 will only happen once, and will fail immediately. I don't think that's worse than removing 4 from some list of candidates, and it's certainly faster than finding all primes beforehand.
Same as with Triptych - nothing with prime-numbers here, same code, other language.
@Beowulf. Try running this code before voting down. It returns prime factors; you just don't understand the algorithm.
Undone the downvote.
the code works ok, but is slow if the incoming number is a prime. I would also only run up to the square and increment by 2. It might be too slow for very big numbers, though.
+1  A:

What's the application?

If you have an upper bound for the number, check if you can just use a table of primes instead ;)

A:

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.

that's what i said, but got voted down :( I guess the problem is that if the number has a really large prime factor (such as itself), then this method must loop all the way up to that number. In a lot of cases though, this method is quite efficient.
Reading back through yours it is the same but the first part of yours is confusing.
Try that on this number 143816789988504044536402352738195137863656439, let me know how efficient this is...
And where are you going to get a box that can run the Sieve on this number???
A:

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 = pfs[-1] # The largest (last) element in the prime factor array
``````

I believe `prime_factors()` runs in O(sqrt(n)) in the worst case. Besides that, it's certainly easy to code and understand.

I do believe this does not work, nor does it retrieve prime-factors, but factors eventually. Where in this code are prime numbers used? d is only natural numbers upcounted, nothing prime there.
Please read and/or run this code before voting it down. It works fine. Just copy and paste. As written prime_factors(1000) will return [2,2,2,5,5,5], which should be interpreted as 2^3*5^3, a.k.a. the prime factorization.
I'm sorry, did an error in converting the code to C#, put one line more into the second while loop. Undone the downvote.
no problem - thanks for correcting.
"runs in `O(sqrt(n))` in the worst case" - No, it runs in `O(n)` in the worst case (e.g. when `n` is prime.)
A:

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.

``````var largestPrimeFactor;
if(n mod 2 == 0)
{
largestPrimeFactor = 2;
n = n / 2 while(n mod 2 == 0);
}
if(n mod 3 == 0)
{
largestPrimeFactor = 3;
n = n / 3 while(n mod 3 == 0);
}

multOfSix = 6;
while(multOfSix - 1 < n)
{
if(n mod (multOfSix - 1) == 0)
{
largestPrimeFactor = multOfSix - 1;
n = n / largestPrimeFactor while(n mod largestPrimeFactor == 0);
}

if(n mod (multOfSix + 1) == 0)
{
largestPrimeFactor = multOfSix - 1;
n = n / largestPrimeFactor while(n mod largestPrimeFactor == 0);
}
multOfSix+=6;
}
``````

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.