Take the 2-minute tour ×

I am trying to write a program to find the largest prime factor of a very large number, and have tried several methods with varying success. All of the ones I have found so far have been unbelievably slow. I had a thought, and am wondering if this is a valid approach:

long number = input;

    number = number / getLowestDivisiblePrimeNumber();

return number;

This approach would take an input, and would do the following:

200 -> 100 -> 50 -> 25 -> 5 (return)

90 -> 45 -> 15 -> 5 (return)

It divides currentNum repeatedly by the smallest divisible number (most often 2, or 3) until currentNum itself is prime (there is no divisible prime number less than the squareroot of currentNum), and assumes this is the largest prime factor of the original input.

Will this always work? If not, can someone give me a counterexample?


EDIT: By very large, I mean about 2^40, or 10^11.

share|improve this question
I'd like to see the implementation of your magical notPrime() function. :) –  Greg Hewgill Dec 9 '09 at 22:14
heh, that's easy: notPrime(n) = (getLowestDivisiblePrimeNumber(n) == n) . –  Carl Smotricz Dec 9 '09 at 22:26
To be honest, I use while(true) there, it was just easier to explain this way. My getLowestDivisiblePrime method refers to an ArrayList<Long> primeList; If there is no divisible prime number in primeList, it finds the next prime number to add to primeList, and continues doing so until it either finds a prime that 'number' is divisble by (and will later refer to a larger list of primes), or until the largest prime in primeList is greater than the sqaureroot of 'number'. No magic there, though I do hope it to be fairly efficient. =P –  Jonathan Dec 9 '09 at 22:28

5 Answers 5

up vote 14 down vote accepted

This will always work because of the Unique Prime Factorization Theorem.

share|improve this answer
Thank you for the cite. =) –  Jonathan Dec 9 '09 at 22:11
For corner cases, 0 and 1 are neither prime nor composite, and given that long is signed, you'll need to figure out how you want to handle negative numbers. –  Andrew Dalke Dec 9 '09 at 22:15

The method will work, but will be slow. "How big are your numbers?" determines the method to use:

share|improve this answer
I'm impressed by your references to algorithms I've never heard of, but: Are not these algorithms much better suited for finding all prime numbers up to a given limit, than for factoring a single number? –  Carl Smotricz Dec 9 '09 at 22:24
I agree with Carl. While I cannot state this as fact (I have not studied on the above mentioned methods), I believe this to be a very effecient method for finding the largest prime factor. How I implement notPrime() -or rather, !prime()- is another matter entirely. –  Jonathan Dec 9 '09 at 22:34
@Jonathan: How big is "very large"? –  280Z28 Dec 9 '09 at 22:40
very large is about 2^40. =) –  Jonathan Dec 9 '09 at 22:43
That falls under "quite small" - easy to factor in milliseconds. Go with Richard Brent's algorithm. –  280Z28 Dec 9 '09 at 22:51

You are trying to find the prime factors of a number. What you are proposing will work, but will still be slow for large numbers.... you should be thankful for this, since most modern security is predicated on this being a difficult problem.

share|improve this answer
On the dot! The first one that comes to mind is RSA. –  Paul Lammertsma Dec 9 '09 at 23:00

Certainly it will work (see Mark Byers' answer), but for "very large" inputs it may take far too long. You should note that your call to getLowestDivisiblePrimeNumber() conceals another loop, so this runs at O(N^2), and that depending on what you mean by "very large" it may have to work on BigNums which will be slow.

You could speed it up a little, by noting that your algorithm need never check factors smaller than the last one found.

share|improve this answer
I will do that, thank you. =) –  Jonathan Dec 9 '09 at 22:37
Though to be picky, it does say 'long' and uses 'Java' in the question tag, so that's only 2**63 and not a BigNum sort of problem. On the other hand, documentation lies. :) –  Andrew Dalke Dec 9 '09 at 22:53
@dalke: Ack. Seeing the words "very large" kinda stuck me in a rut. And I think the improved version can run in (kinda slow) linear time, though the method the OP suggests will use a lot of space... –  dmckee Dec 9 '09 at 23:13

From a quick search I just did, the fastest known way to factor a number is by using the Elliptic Curve Method.

You could try throwing your number at this demo: http://www.alpertron.com.ar/ECM.HTM .

If that convinces you, you could try either stealing the code (that's no fun, they provide a link to it!) or reading up on the theory of it elsewhere. There's a Wikipedia article about it here: http://en.wikipedia.org/wiki/Lenstra_elliptic_curve_factorization but I'm too stupid to understand it. Thankfully, it's your problem, not mine! :)

share|improve this answer

Your Answer


