PRIMEOB - Editorial

general
1

PROBLEM LINK:

Contest

Practice

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

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

3

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.

4

@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…