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: introductory

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'

# Python3 program Miller-Rabin primality test 
import random  
  
# Utility function to do 
# modular exponentiation. 
# It returns (x^y) % p 
def power(x, y, p): 
      
    # Initialize result 
    res = 1;  
      
    # Update x if it is more than or 
    # equal to p 
    x = x % p;  
    while (y > 0): 
          
        # If y is odd, multiply 
        # x with result 
        if (y & 1): 
            res = (res * x) % p; 
  
        # y must be even now 
        y = y>>1; # y = y/2 
        x = (x * x) % p; 
      
    return res; 
  
# This function is called 
# for all k trials. It returns 
# false if n is composite and  
# returns false if n is 
# probably prime. d is an odd  
# number such that d*2<sup>r</sup> = n-1 
# for some r >= 1 
def miillerTest(d, n): 
      
    # Pick a random number in [2..n-2] 
    # Corner cases make sure that n > 4 
    a = 2 + random.randint(1, n - 4); 
  
    # Compute a^d % n 
    x = power(a, d, n); 
  
    if (x == 1 or x == n - 1): 
        return True; 
  
    # Keep squaring x while one  
    # of the following doesn't  
    # happen 
    # (i) d does not reach n-1 
    # (ii) (x^2) % n is not 1 
    # (iii) (x^2) % n is not n-1 
    while (d != n - 1): 
        x = (x * x) % n; 
        d *= 2; 
  
        if (x == 1): 
            return False; 
        if (x == n - 1): 
            return True; 
  
    # Return composite 
    return False; 
  
# It returns false if n is  
# composite and returns true if n 
# is probably prime. k is an  
# input parameter that determines 
# accuracy level. Higher value of  
# k indicates more accuracy. 
def prime_or_composite( n, k=10): 
      
    # Corner cases 
    if (n <= 1 or n == 4): 
        return "Composite"; 
    if (n <= 3): 
        return "Probable Prime"; 
  
    # Find r such that n =  
    # 2^d * r + 1 for some r >= 1 
    d = n - 1; 
    while (d % 2 == 0): 
        d //= 2; 
  
    # Iterate given nber of 'k' times 
    for i in range(k): 
        if (miillerTest(d, n) == False): 
            return "Composite"
  
    return "Probable Prime"; 

# Miller-Rabin primality test 

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"