There is this Miller-Rabin primality test. http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
I have tried this many times and everytime it succeed when 10 iterations in algorithm were used. On Sun, Apr 14, 2013 at 11:10 PM, payel roy <smithpa...@gmail.com> wrote: > I read that.. but still not understanding how you would solve for a number > having 1000 digits. Would be great if you can explain with an example. > > > On 14 April 2013 22:48, Bharat Singhvi <bharatsinghvi.1...@gmail.com>wrote: > >> http://en.wikipedia.org/wiki/AKS_primality_test >> >> >> On Sun, Apr 14, 2013 at 10:46 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. >>> >>> >>> >> >> >> >> -- >> Regards >> Bharat Singhvi >> M.Tech Final Year, >> Dept. of Computer Science and Engineering, >> IIT Bombay. >> >> -- >> 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. >> >> >> > > -- > 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. > > > -- Shashwat Kumar Third year Undergraduate student Department of Computer Science and Engineering IIT Kharagpur -- 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.
