Checking primality of very large numbers in Python

Question

What would be the fastest way to check if a given large number is prime? I'm talking about numbers the size of around 10^32. I've tried the algorithm from the great answer by @MarcoBonelli which is:

from math import sqrt; from itertools import count, islice

def isPrime(n):
    return n > 1 and all(n%i for i in islice(count(2), int(sqrt(n)-1)))

but it gives the error of Stop argument for islice() must be None or an integer: 0 <= x <= sys.maxsize when used against such large numbers. What would be a different, fast way to do it then?

Answer 1

For a moderately large number I would use Miller-Rabin's Primality test. You can find Python code for it here: https://rosettacode.org/wiki/Miller%E2%80%93Rabin_primality_test#Python

Note that the algorithm is probabilistic in nature, but applying it a number of time will guarantee correct answers with very high probability.

If you are absolutely set on using a trial division based method, I would recommend you multiply a large number of small primes and store the resulting composite number. Then you can take the Greatest Common Divisor (GCD) using a standard algorithm (such as 'fraction.gcd'). If the answer is not 1, then the number tested is definitely not prime. Usually you would then apply the Miller-Rabin test above to determine whether it is prime.