### PROBLEM LINK:

**Author:** Roshan Choudhary

### DIFFICULTY:

Easy### PREREQUISITES:

Number Theory , [Fermat primality test][5]### 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.Python Code:

```
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"
```