from random import randrange

def probably_prime(n, k):
"""Return True if n passes k rounds of the Miller-Rabin primality
test (and is probably prime). Return False if n is proved to be
composite.

"""
if n < 2: return False

r, m = 0, n - 1
while m % 2 == 0:
    r += 1
    m //= 2
for _ in range(k):
    a = randrange(2, n - 1)
    x = pow(a, m, n)
    if x == 1 or x == n - 1:
        continue
    for _ in range(r - 1):
        x = pow(x, 2, n)
        if x == n - 1:
            break
    else:
        return False
return True