Part 6 of 28 in Maths - Beginner set 01  

Verify Prime Number by admin

Problem statement

Given a number, verify whether its prime or not


First line of input will contain a number N = number of test cases. Next N lines will contain number n as test case where 0<=n<=1000000000


For each input case, print "PRIME" if the number is prime, else print "NOT PRIME" (quotes for clarity)

Sample Input
Sample Output
1) Are you trying to divide by all integers till n or n/2 ?  This will exceed the time limit. Think of a better algorithm. 

2) 1 is not a prime number. 

3) Are you good if number is a perfect square?

4) Make sure you are not printing any extra spaces or end-of-line characters. 

There are several algorithms for testing whether a number is prime or not.

Some algorithms are faster but a bit complex to understand. Easier algorithms can be coded easily, but are comparatively slow.

Here, we discuss about Trial Division Method, which is simple to understand and code.

A number is said to be Prime if it has no other divisors except 1 and itself.

So, in order to check for primality, we can try dividing the number with all possible divisors it could be divided completely. All possible divisors include the numbers from 2 to square root of that particular number we are interested.

It is sufficient to check only for divisors less than or equal to sqrt (n) because if n = a*b, then a and b can't both exceed the square root of n.

If we find that our number can be divided by any of the possible divisors, we can terminate returning false, means the number is Not Prime

If we successfully finish checking with all those divisors, we return true, i.e. the number is Prime.

editorial written by shivshnkr


using namespace std;

/* function to check if the given number is prime or not */
bool prime_check(int n)
    if (n < 2) {
        /* explicit handling of numbers less than 2, since 0 
           and 1 are not prime */
           return false;
    /* checking divisibility with all possible divisors */
    /* all possible divisors could be numbers between  
       2 and sqrt(n) (both inclusive)  */
	for (int div = 2; div <= sqrt (n); div++) {
		if (n % div == 0) {
		/* Number is divisible by div so not prime */
                    return false;
	/* Passed tests with all possible divisors
	   and hence the number is prime */
	return true;

int main()
	int test;
	int num;
	/* read number of tests from stdin */
	cin >> test; 
	/* loop for all test cases */ 
	while (test != 0) {
		cin >> num;
		if (prime_check(num) == true) {
			/* The given number is prime */
			cout << "PRIME" << endl;
		} else {
			/* The given number is not prime */
			cout << "NOT PRIME" << endl;
		test--; /* decrement test counter */ 
	return 0;

featured solution by shivshnkr

To try out your code

Sign in

Sign up