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)

4
0
1
2
3

NOT PRIME
NOT PRIME
PRIME
PRIME

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

#include<iostream>
#include<cstdio>
#include<cmath>

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