### MinusRatingPhobia's blog

By MinusRatingPhobia, history, 3 years ago,

Hi All, I was wondering how can we check whether a number is prime or not if it is let's say a 30 digit number. I am trying to solve this for few days now I would really appreciate help of any sort. Thank you.

| Write comment?
 » 3 years ago, # | ← Rev. 2 →   +24 Java's BigInteger.isProbablePrime(int certainty)
 » 3 years ago, # |   -22 I use this funcution bool isPrime(int n) { if (n < 2) return false; if (n == 2) return true; if (n % 2 == 0) return false; for (int i = 3; i <= sqrt(n); i+=2) { if (n % i == 0) return false; } return true; } 
•  » » 3 years ago, # ^ |   +15 Hi, Thanks for replying but it won't work for 30 digit number.
•  » » 3 years ago, # ^ |   +7 It will give tle
 » 3 years ago, # |   +28 Any deterministic algorithm (AKS) is probably too slow to be used practically. You can use Miller-Rabin primality testing though with a high probability. https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test