Cacher is the code snippet organizer for pro developers

def millerRabin(n, k = 5):
    if n <= 3 or n % 2 == 0: return n == 2 or n == 3
	d = n - 1
	s = 0
	while d > 0 and d % 2 == 0:
		d = d / 2
		s = s + 1

	def millerRabinPass(a, s, d, n):
		x = pow(a, d, n)
		if x == 1: return True
		for i in xrange(s - 1):
			if x == n - 1: return True
			x = (x * x) % n
		return x == n - 1

	return all(millerRabinPass( random.randint( 2, n - 2 ), s, d, n) for _ in xrange(k))