def is_prime(n, k=64):
    if n == 2:
        return True
    if n < 2 or n % 2 == 0:
        return False
    for i in range(3, 2048):
        if n % i == 0:
            return False
    s = 0
    d = n - 1
    while True:
        q, r = divmod(d, 2)
        if r == 1:
            break
        s += 1
        d = q
    for i in range(k):
        a = random.randint(2, n - 1)
        if check_candidate(a, d, n, s):
            return False
    return True