public static boolean isPrime(int N) {
if (N == 1) return false;
if (N == 2) return true;
else if (N % 2 == 0) return false;
// N 이 약수라면, 루트N 이하의 약수를 가지므로 루트N까지만 검사.
//짝수도 위에서 이미 가지치기 하였으므로 2씩 증가
for (int i = 3; i <= Math.sqrt(N); i+= 2) {
if (N % i == 0) {
return false;
}
}
return true;
}