Trial division is fine for small numbers, perhaps up to 10 digits. But think for a moment about what that would take for a 1000 digit number. The square root of such a number is 500 digits. There are about 10^496 primes smaller than 10^500. If you have a billion computers each checking a billion of those numbers every second, it would take 10^471 years to complete the trial division. For reference, the current age of the universe is about 1.4*10^10 years.
There must be a better way. And there is. The most commonly used way to determine if a number is prime, to a sufficiently high confidence, is using the Miller Witness test. Each iteration of this test can be performed by a computer in a fraction of a second for a 1000 digit number. If any test fails, the number is composite. Each test which passes increases the confidence that the number is prime. Trying ten witness values is usually considered sufficient to accept that the number is prime. If you need to prove that a number is prime beyond the shadow of a doubt, Elliptical Curve Primality Proof (ECPP) is an outstanding algorithm. "Primo" is a Windows-based implementation of ECPP. See http://primes.utm.edu/prove/index.html for more information. Don On Apr 14, 1:16 pm, payel roy <smithpa...@gmail.com> wrote: > You are to test whether a number if prime or not. > > Digit of that number can be as large as 1000. How do you do that? > > I was thinking of basic idea. > > a) First I shall calculate all primes which is less than the square root of > the given number > b) Will try to divide that given number by all this primes. > > Not sure how do I calculate the (a) part since number is huge. > > Any idea is welcome. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
