import random
import time


def lcg(seed, a=1664525, c=1013904223, m=2**32):
    while True:
        seed = (a * seed + c) % m
        yield seed  # Produces an infinite stream of numbers


rand_gen = lcg(42)


def randint(a, b) -> int:
    return next(rand_gen) % (b - a + 1) + a


def milrab(n: int, iter: int = 5) -> bool:
    "Miller-Rabin probabilistic primality test"

    # These should need no further introduction
    if n < 2:
        return False
    if n in (2, 3):
        return True
    if n % 2 == 0:
        return False

    # Keep in mind that here we know that m will be an even number
    m = n - 1
    k = 0

    # Executed at least once
    while m % 2 == 0:
        m //= 2  # Int divide for int result type
        k += 1

    for _ in range(iter):
        a = randint(2, n - 2)  # Any integer in range 1 < a < n - 1
        b = pow(a, m, n)

        # Valid only for the first iteration
        if b == 1 or b == n - 1:
            continue  # Likely a prime

        # The rest, we start from 0
        for _ in range(k - 1):
            b = pow(b, 2, n)
            if b == n - 1:
                break  # May be prime
            if b == 1:  # For sure not prime
                return False

        else:  # Python way to branch if loop never calls break
            return False

    return True


assert milrab(53, 1) == True
assert milrab(53, 2) == True
assert milrab(53, 3) == True
assert milrab(53, 4) == True
assert milrab(203, 10) == False

assert milrab(10, 4) == False

start = time.perf_counter()
primes = []
for p in range(2**15, 2**16):
    if milrab(p, 10):
        primes.append(p)
end = time.perf_counter()
print(f"Time taken: {end - start:.6f} seconds")


for k in range(10):
    assert milrab(53, k) == True