public static boolean isPrime(int n) { if (n == 2) return true; if (n % 2 == 0 || n == 1) return false; long limit = (long)Math.sqrt(n); for (int i = 3; i <= limit; i += 2) if (n % i == 0) return false; return true; }