1. 가장 일반적인 방법
public static void main(String[] args) {
int num = 23;
boolean isPrime = true;
for (int i = 2; i <= num / 2; i++) {
if (num % i == 0) {
isPrime = false;
break;
}
}
System.out.println(isPrime); // true
}
i 를 num 까지 돌리지 않고 절반까지만 해도 값을 충분히 구할 수 있기 때문에, 반복문 범위를 i <= num / 2 로 설정했다.
num % i == 0 이면, i는 자신의 약수이기 때문에 소수가 아니므로 false로 하고 바로 break 처리
2. 제곱근을 통해 소수 판별하는 방법
소수 판별을 위해 n의 제곱근까지만 확인하면 된다.
예를 들어, 16 이라는 합성수가 있다.
16의 약수로는 1, 2, 4, 8, 16 이 있다.
1 * 16 = 16
2 * 8 = 16
4 * 4 = 16
8 * 2 = 16
16 * 1 = 16
위 식들은 둘 중 적어도 하나는 n 의 제곱근보다 작거나 같다.
따라서, n 의 제곱근까지만 확인하면 소수를 판별할 수 있다!
public static void main(String[] args) {
int num = 23;
boolean isPrime = true;
for (int i = 2; i <= Math.sqrt(num); i++) {
if (num % i == 0) {
isPrime = false;
break;
}
}
System.out.println(isPrime); // true
}
3. 에라토스테네스의 체
에라토스테네스의 체는 "소수가 되는 수의 배수를 지우면 남은 건 소수가 된다" 는 알고리즘이다.
소수가 무엇인지 찾을 필요가 없으며, 2부터 자기 자신을 제외한 배수가 되는 것을 지우면 된다.
public static void main(String[] args) {
int num = 10;
boolean[] check = new boolean[num+1];
// 소수 이면 false, 소수가 아니면 true
check[0] = true;
check[1] = true;
for (int i = 2; i < Math.sqrt(num); i++) {
if (!check[i]) {
for (int j = i * 2; j <= num; j += i) {
check[j] = true;
}
}
}
for (int i = 1; i <= num; i++) {
if (!check[i]) {
System.out.print(i + " "); // 2 3 5 7
}
}
}