URI Problem 1221 Solution Fast Prime Number - URI Online Judge Solution

URI Online Judge Solution 1221 Fast Prime Number Using C++, Python Programming Language.

Mary knows that a Prime Number is a number that is divisible only by 1 (one) and by itself. For example the number 7 is Prime, because it can be divided only by 1 and by 7. So she asked you to write a program that reads many numbers ​​and inform if each one of these numbers are prime or not. But Patience is not one of the virtues of Mariazinha, so she wants that the execution of all test cases (instances) created by herself happen at the maximum in one second, because she hates waiting :>).

Input

The first input line contains an integer N (1 ≤ N ≤ 200), corresponding to the number of test cases. Follow N lines, each one containig one integer number X (1 < X < 231) that can be or not a prime number

Output

For each test case output the message “Prime” or “Not Prime” according to the to following example.

Sample Input	Sample Output
3 123321 123 103	Not Prime Not Prime Prime

Solution Using C++:

#include<iostream>
#include<math.h>
using namespace std;
int CheckPrime(int num);
int main()
{
    int T,num;

    cin>>T;
    while(T--)
    {
        cin>>num;
        if(CheckPrime(num))
            cout<<"Prime"<<endl;
        else
            cout<<"Not Prime"<<endl;
    }
    return 0;
}
int CheckPrime(int num)
{
    int p,i;
    p=0;
    for(i=2; i<sqrt(num); i++)
    {
        if(num%i == 0)
        {
            p++;
        }
        if(p==2) break;
    }
    if(p>0)
        return 0;
    else
        return 1;
}