 # PRIMEOB - Editorial

Contest

Practice

Author: Roshan Choudhary

Easy

### 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.

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

why last subtask gives wa ?implemented fermat and miller rabin test both gives wa,many other submissions also give same result wa in last subtask
http://www.codechef.com/viewsolution/7240854

the test cases are definitely faulty. Even the submission which prints PRIME for n==1 gets passed easily. Can’t rely on such contests and questions.

@likecs: Have a look at the constraints…it says N>=2 and the test cases are set accordingly…I hope it will clear your doubts…