Primality test using random.
from random import randint def pow(a,n,m): p=1 for _ in range(n): p*=a p%=m return p def isprime(n): d=n-1 s=0 while d%2==0: s+=1 d/=2 for _ in range(5): a=randint(2,n-2) x=pow(a,d,n) if x==1 or x==n-1: continue c=False for _ in range(s-1): x=pow(x,2,n) if x==1: return False if x==n-1: c=True break if c: continue return False return True