MinusRatingPhobia's blog

How to check if a given 30 digit number is prime ?
By MinusRatingPhobia, history, 4 years ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it +24 Vote: I do not like it

Java's BigInteger.isProbablePrime(int certainty)

→ Reply
»
4 years ago, # |
  Vote: I like it -22 Vote: I do not like it

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;
}
→ Reply
»
4 years ago, # |
  Vote: I like it +28 Vote: I do not like it

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

→ Reply