Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
246 views
in Technique[技术] by (71.8m points)

java - Problems with prime numbers

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.

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Answer

0 votes
by (71.8m points)

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


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...