i hv tried checking primality of a number bt testing till sqrt of number bt its too time consuming for big numbers… Fermats test involves expotential terms and is tedious to implement for a large number(say for 10^10).
I have heard about AKS algortithm invented at IIT Kanpur in 2002 which is deterministic and pretty fast as well. works in (log(n))^x where n is the number and x is some constant between 7.5 and 12 depending on the implementation. here is the wikipedia link
Miller Rabin Test is good for numbers till 10^18 , i can say with experience .
Particularly note this line in wiki link :
if n < 1,373,653, it is enough to test a = 2 and 3; if n < 9,080,191, it is enough to test a = 31 and 73; if n < 4,759,123,141, it is enough to test a = 2, 7, and 61; if n < 1,122,004,669,633, it is enough to test a = 2, 13, 23, and 1662803; if n < 2,152,302,898,747, it is enough to test a = 2, 3, 5, 7, and 11; if n < 3,474,749,660,383, it is enough to test a = 2, 3, 5, 7, 11, and 13; if n < 341,550,071,728,321, it is enough to test a = 2, 3, 5, 7, 11, 13, and 17.
If you use java, the BigInteger class has an in built
isProbablePrime method, which is quite fast and accurate.
@xylon97 : That’s correct , if you use the BigInteger’s isProbablePrime method with a certainity factor about 100 , then it returns correct answers for all integers in range of “long” and is quite fast also .
it uses Miller-Rabin
@betlista @vineetpaliwal can you tell me what is the probablity that Rabin-Miller gives the correct answer. I know it is very high and will suffice for all practical purposes but it is still non-deterministic.
ds rtedgsd fgdfg dgdsfgdf
dfg dg hrthfhdfhjgj