text: from random import randrange 
  
  def MillerRabin (p):
  	d = p - 1
  	r = 0
  	while d % 2 == 0:
  		d //= 2
  		r += 1
  	a = randrange(2, p - 1)
  	x = (a ** d) % p
  	if x == 1 or x == p - 1:
  		return True
  	while r > 1:
  		x = (x * x) % p
  		if x == 1:
  			return False
  		if x == 1:
  			return False
  		if x == p - 1:
  			return True
  		r -= 1
  	return False