//Miller-Rabin (Primality Test)

import random
def power(x,n):
    if(n==0):
            return 1
    elif(n%2==0):
            return (power(x,n//2)*power(x,n//2))
    else:
            return (x*(power(x,n//2))*(power(x,n//2)))

def millir(n,d):
    a=2+random.randint(1,n-4)
    x=(power(a,d))%n
    if(x==1 or x==n-1):
            return True
    while(d==n-1):
            x=(x*x)%n
            if(x==1):
                    return False
            if(x==n-1):
                    return True


def isprime(n,k):
    if(n==1):
            return False
    if(n==2):
            return True
    if(n%2==0):
            return False
    d1=0
    for d in range(3,10000,2):
            for r in range(1,10000):
                    if(n-1==d*(2**r)):
                            d1=d
                            break
            if(d1==d):
                break
    for i in range(2):
            if(millir(n,d)==False):
                    return False
    return True
print(isprime(21,2))