MinusRatingPhobia's blog

By MinusRatingPhobia, history, 3 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.

| Write comment?
»
3 years ago, # |
Rev. 2   Vote: I like it +24 Vote: I do not like it

Java's BigInteger.isProbablePrime(int certainty)

»
3 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;
}
»
3 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