import random
    
def mul(a,b,m):
    if b == 1:
        return a
    if b == 0:
        return 0
    if b%2 == 0:
        t = mul(a, b/2, m)
        return (2 * t) % m
    return (mul(a, b-1, m) + a) % m

def Bpow(a,b,m):
    if b == 0:
        return 1
    if b%2 == 0:
        t = Bpow(a, b/2, m)
        return mul(t,t,m)%m
    return (mul(Bpow(a,b-1,m),a,m)) % m

def Nod(a,b):
    if (b==0):
        return a
    return Nod(b, a%b)

def Ya(a,b,r):
    t = 0
    while a%2 == 0:
        t += 1
        a /= 2
    if t%2 != 0:
        if (b%8 == 3) or (b%8 == 5):
            r = -r
    if (a%4 == b%4) and (b%4 == 3):
        r = -r
    c = a
    a = b%c
    b = c
    if a != 0:
        Ya(a,b,r)
    return r

def El(a,b):
    r=1
    #if Bpow(a,((b-1)/2)-1,((b-1)/2))%b == Ya(a,b,r):
    if (a^((b-1)/2))%b == Ya(a,b,r):
        return true
    return false

n = 97
com=0
nc=0
i=0
if n == 2:
    print n, "is Prime"
elif n%2 == 0:
    print "n has to be odd"
else:
    while i < 100:
        a=random.randint(1, n)
        if Nod(a,n) > 1:
            com += 1
        else:
            if El(a,n):
                nc += 1
            else:
                com += 1
        i+=1
print "Composite due to 100 experiments: ", com
print "Prime/unknown due to 100 experiments: ", nc