[JAVA] 소수 판별 알고리즘 모음

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
            }
        }
    }