#!/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, n):
	if rand_int ** odd_no == 1 % n:
		for i in range(0, n):
			if rand_int ** ( ( 2**i) * odd_no ) == -1 % n:
				continue
			else:
				break
				return "Prime"
	else:
		return "Prime"
	return "Composite"

number = 75

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

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

print freqCheck(k, odd_no, n)