#!/usr/bin/env python
#Author: Shriphani Palakodety
#Mail: spalakod@purdue.edu
#!/usr/bin/python
#Miller Rabin Primality Test.
#Author: Shriphani Palakodety a.k.a PSP

#Now comes one of the world's fastest primality tests:

from random import randint

def twoPower(n):
        s = 0
        while n > 0:
                if n % 2 == 0:
                        n = n / 2
                        s += 1
                else:
                        d = n
                        break
        return s, d

def randGen(n):
        return randint(0, n)

def moduloCheck(rand_int, odd_no, s, n):
        a = True
        print rand_int
        if (rand_int ** odd_no - 1) % n == 0:
                a = False
        for i in xrange(0, s):
                if (rand_int ** ((2**i) * odd_no) + 1) % n==0:
                        a = False
        print a
        if a:
                return "Composite"
        else:
                return "Prime"
        
number = 75

n = twoPower(number- 1)[0]
odd_no = twoPower(number - 1)[1]
k = 31

def freqCheck(k, odd_no, n):
        freq_list = []
        for i in range(0, k):
                freq_list.append(moduloCheck(randint(0,number-1), odd_no, n, number ))
        if freq_list.count("Prime") > freq_list.count("Composite"):
                return "Prime"
        else:
                return "Composite"

print freqCheck(k, odd_no, n)