Cacher is the code snippet organizer for pro developers

//A number is prime when it is just divisible by 1 and its grater than 1

//ALGORITHM: compare all the numbers smaller or equal to the square root of n!
//Why? Square root of n is sufficient because for each number a that divides n evenly,
  //there exists a number b such that a*b = n. 
  // If a > square root of n then be has to be smaller than the square root of n. 


import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. */

        Scanner s = new Scanner(System.in);
        
        int testcases = s.nextInt();
        int test;
        while(testcases > 0){
            isPrime(s.nextInt());
            testcases --;
        }

    }

    public static void isPrime(int number){
        if(number == 1){
            System.out.println("Not prime");
            return;
        }
        for(int i = 2; i<=Math.sqrt(number); i++){
            if(number%i == 0){
                System.out.println("Not prime");
                return;
            }
        }
        System.out.println("Prime");
    }
}