import java.util.*;

public class PrimeNumber {

    private List<Integer> sieve(int m) {
        List<Integer> p = new ArrayList<Integer>();
        if (m <= 1) { return p; }
        boolean[] ary = new boolean[m+1];
        Arrays.fill(ary, 2, m+1, true);
        for (int i = 2; i <= m; i++) {
            if (ary[i]) {
                p.add(i);
                for (int j = i * 2; j <= m; j += i) {
                    ary[j] = false;
                }
            }
        }
        return p;
    }

    private boolean checkPrime(int n, List<Integer> p) {
        if (p.size() == 0) { return true; }
        for (int i = p.size()-1; i >= 0; i--) {
            if (n % p.get(i) == 0) { return false; }
        }
        return true;
    }

    public String isPrime(int n) {
        if (n <= 1) { return "Not prime"; }
        int m = (int)Math.sqrt(n);
        List<Integer> primes = sieve(m);
        return checkPrime(n, primes) ? "Prime" : "Not prime";
    }
}