java - Problems with prime numbers

Question

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;

while(notPrime(number))
{
    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.

Answer 1

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

• Less than 2^16 or so: Lookup table.
• Less than 2^70 or so: Sieve of Atkin. This is an optimized version of the more well known Sieve of Eratosthenes. Edit: Richard Brent's modification of Pollard's rho algorithm may be better in this case.
• Less than 10^50: Lenstra elliptic curve factorization
• Less than 10^100: Quadratic Sieve
• More than 10^100: General Number Field Sieve