from random import randrange
def is_prime(n, trials=6):
""" Miller-Rabin probabilistic prime test.
"""
if n < 2:
return False
i = 0
while i < trials:
i+=1
a = randrange(1, n)
if pow(a, n-1, n) != 1: # (a**(n-1)) % n
return False
return True
# or as a tiny-font-one-liner
def is_prime(n, trials=6):
return n >= 2 and (trials == 0 or (pow(randrange(1, n), n-1, n) == 1 and is_prime(n, trials - 1)))