If time complexity is not the issue and you just need to find the square root of the number and iterate over [2,sqrt(num)] then one way in which it can be done is by using BigInteger class of Java.
You will need to write your own method to compute square root of BigInteger. Read this<http://www.java-examples.com/find-square-root-biginteger-example> . If you need AKS implementation, here is a pointer<http://fatphil.org/maths/AKS/> . There are some probability based primalty testing algorithms which you can look into. Link1 <http://mathworld.wolfram.com/LucasPseudoprime.html> Link2<http://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html> Java has inbuilt method that uses the algorithm described in Link2 above. The method is - isProbablePrime() and it works with BigIntegers. Hope this helps 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. > > > -- 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.
