Блог пользователя MinusRatingPhobia

How to check if a given 30 digit number is prime ?
Автор MinusRatingPhobia, история, 4 года назад, По-английски

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.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
4 года назад, # |
← Rev. 2   Проголосовать: нравится +24 Проголосовать: не нравится

Java's BigInteger.isProbablePrime(int certainty)

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится -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;
}
→ Ответить
»
4 года назад, # |
  Проголосовать: нравится +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

→ Ответить