Author: Roshan Choudhary
PREREQUISITES:Number Theory , [Fermat primality test]
PROBLEM:Given a number find wheter it is prime or not.
EXPLANATION:If we want to test whether p is prime, then we can pick random a's in the interval and see whether the equality holds. If the equality does not hold for a value of a, then p is composite. If the equality does hold for many values of a, then we can say that p is probably prime.The complexity is O(log(N)) because we need to compute a^N and that takes O(log(N)) time.
from random import randint def fun(N): if N > 1 : for _ in xrange(5): Num=randint(1,N-1) if pow(Num,N-1,N)!=1: return False return True return False for _ in xrange(input()): if(fun(input())): print "PRIME" else: print "COMPOSITE"