Check if given numbers are prime numbers. 
If number N is prime ```return "Probable Prime"``` else ``` return "Composite"```. 
HINT: Upper bount is really big so you should use an efficient algorithm.

Input
  1 < N ≤ 10^(100)

Example
  prime_or_composite(2)  # should return Probable Prime
  prime_or_composite(200)  # should return Composite

Difficulty: EASY
Tags: Mathematics

Starter code:
def prime_or_composite(n):
	

Solutions:
def prime_or_composite(n):
	if n < 4:
		return 'Probable Prime'
	if n % 2 == 0:
		return 'Composite'
	(d, r) = (n - 1, 0)
	while d % 2 == 0:
		(d, r) = (d // 2, r + 1)
	for a in [2, 31]:
		x = pow(a, d, n)
		if x in (1, n - 1):
			continue
		for _ in range(r - 1):
			x = pow(x, 2, n)
			if x == 1:
				return 'Composite'
			if x == n - 1:
				break
		else:
			return 'Composite'
	return 'Probable Prime'


_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

def try_base(a, d, n, s):
	if pow(a, d, n) == 1:
		return False
	for i in range(s):
		if pow(a, 2 ** i * d, n) == n - 1:
			return False
	return True

def miller_rabin(n):
	if n in _primes:
		return True
	if any((not n % p for p in _primes)):
		return False
	(d, s) = (n - 1, 0)
	while not d & 1:
		(d, s) = (d >> 1, s + 1)
	return not any((try_base(a, d, n, s) for a in _primes))

def prime_or_composite(n):
	return 'Probable Prime' if miller_rabin(n) else 'Composite'


def prime_or_composite(n):
	from random import randrange
	if n == 2:
		return 'Probable Prime'
	if not n & 1:
		return 'Composite'

	def check(a, s, d, n):
		x = pow(a, d, n)
		if x == 1:
			return 'Probable Prime'
		for i in range(s - 1):
			if x == n - 1:
				return 'Probable Prime'
			x = pow(x, 2, n)
		return x == n - 1
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for i in range(2, 20):
		a = randrange(2, n)
		if not check(a, s, d, n):
			return 'Composite'
	return 'Probable Prime'


import random

def prime_or_composite(q, k=100):
	q = abs(q)
	if q == 2:
		return 'Probable Prime'
	if q < 2 or q & 1 == 0:
		return 'Composite'
	d = q - 1 >> 1
	while d & 1 == 0:
		d >>= 1
	for i in range(k):
		a = random.randint(1, q - 1)
		t = d
		y = pow(a, t, q)
		while t != q - 1 and y != 1 and (y != q - 1):
			y = pow(y, 2, q)
			t <<= 1
		if y != q - 1 and t & 1 == 0:
			return 'Composite'
	return 'Probable Prime'


import random

def is_prime(n):
	k = 100
	if n <= 1:
		return False
	elif n == 2:
		return True
	if n % 2 == 0:
		return False
	d = n - 1
	s = 0
	while d % 2 == 0:
		s += 1
		d //= 2
	for i in range(k):
		a = random.randint(1, n - 1)
		if pow(a, d, n) == 1:
			continue
		is_composite = True
		for r in range(s):
			if pow(a, pow(2, r) * d, n) == n - 1:
				is_composite = False
				break
		if is_composite:
			return False
	return True

def prime_or_composite(n):
	return 'Probable Prime' if is_prime(n) else 'Composite'


import random

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def miillerTest(d, n):
	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
		d *= 2
		if x == 1:
			return False
		if x == n - 1:
			return True
	return False

def prime_or_composite(n, k=10):
	if n <= 1 or n == 4:
		return 'Composite'
	if n <= 3:
		return 'Probable Prime'
	d = n - 1
	while d % 2 == 0:
		d //= 2
	for i in range(k):
		if miillerTest(d, n) == False:
			return 'Composite'
	return 'Probable Prime'


from random import randrange

def prime_or_composite(n):
	if n < 10:
		return 'Probable Prime' if n in [2, 3, 5, 7] else 'Composite'

	def miller_test(a, d):
		p = pow(a, d, n)
		if p == 1 or p == n - 1:
			return False
		while d != n - 1 and p != 1 and (p != n - 1):
			p = p ** 2 % n
			d *= 2
		return False if p == n - 1 else True
	d = n - 1
	while d % 2 == 0:
		d >>= 1
	for i in range(8):
		a = randrange(2, n - 1)
		if miller_test(a, d):
			return 'Composite'
	return 'Probable Prime'


import random

def prime_or_composite(num):
	for j in range(20):
		a = random.randint(1, num - 1)
		if pow(a, num - 1, num) != 1:
			return 'Composite'
	return 'Probable Prime'