[C++] HackerRank Day25 Solution

/*
https://www.hackerrank.com/challenges/30-running-time-and-complexity/problem

*/

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    int t;
   
    cin >> t;
   
    for(int i=0; i<t; i++){
        int flag = 1;
        int n;
       
        cin >> n;
       
        if(n <= 1){
            cout << "Not prime" << endl;
            continue;
        }
       
        if(n == 2){
            cout << "Prime" << endl;
            continue;
        }           
        else if((n&1) == 0){                //even number is not prime.
            cout << "Not prime" << endl;
            continue;
        }
       
        for(int i=3; i*i<=n;i++){         
            if(n%i == 0){
                flag = 0;
                break;
            }
        }
       
        if(flag) {
            cout << "Prime" << endl;
            continue;           
        } else {
            cout << "Not prime" << endl;
            continue;           
        }     
    }
     
    return 0;
}