소수를 판별하는 방법들 - Java

소수를 판별하는 방법들

때때로 알고리즘 문제를 풀다 보면 소수를 찾거나 소수의 개수를 구하는 등 특정 수가 소수인지를 판별해야하는 경우가 종종 발생한다. 여기서 소수란 1과 자기 자신으로 나누어 떨어지는 양의 수를 의미한다. 이때 1은 소수가 아니며 2와 3 그리고 5와 같이 1과 자기 자신으로 나누어 떨어지는 수는 소수이다. 이번 글에서는 특정 수가 주어졌을 때 그 수가 소수인지를 판별하는 방법들을 자바 프로그래밍을 통해 알아보고자 한다.

 

 

가장 직관적인 소수 판별 방법

    public boolean isPrime(int n) {
        if (n < 2) {
            return false;
        }

        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                return false;
            }
        }

        return true;
    }

 

가장 직관적인 소수 판별 방법이다. 우선 앞서 말한대로 1은 소수가 아니므로 1차적으로 2 미만의 수는 소수가 아님(false)을 반환해준다. 이후 자기 자신 외로 나누어 떨어지는 수가 있는지를 체크하여 반환해주는데, 자기 자신 외로 나누어 떨어지는 수 중 가장 큰 수는 자기 자신의 수에 대한 제곱근에 가장 가까운 수 Math.sqrt(n)이다. 예를 들어, 9라는 수에서 나누어 떨어지는 수 중 가장 큰 수는 9의 제곱근인 3이다.

 

즉, 2부터 자기 자신의 수까지 나누어 떨어지는 지 체크할 필요없이 2부터 자기 자신의 수에 대한 제곱근에 가장 가까운 수까지만 체크하면 되는 것이다. 혹시 중간에 하나라도 나누어 떨어지는 게 있다면 그 수는 1과 자기 자신의 수 외로 나누어 떨어진 것이므로 소수가 아님(false)을 반환해준다. 이 과정을 거쳤다면 소수이므로 true를 반환해준다.

 

 

에라토스테네스의 체를 이용한 소수 판별 방법

    public boolean isPrime(int n) {
        if (n < 2) {
            return false;
        }

        boolean[] nums = new boolean[n + 1]; // 최초 0 ~ n 까지의 모든 수가 소수(false)라고 가정한다.
        nums[0] = nums[1] = true; // 0과 1은 소수가 아니다.
        for (int i = 2; i * i <= n; i++) {
            if (!nums[i]) { // i가 소수인 경우
                for (int j = i * i ; j <= n; j += i) { // i 자기 자신을 제외한 i의 배수의 수는 소수가 아니다. 
                    nums[j] = true;
                }
            }
        }

        return !nums[n]; // nums[n]이 소수(false)일 경우 true 반환
    }

 

해당 방법은 고대 그리스 수학자 에라토스테네스가 발견한 소수를 찾는 방법이다. 이 알고리즘은 위키백과에 따르면 다음과 같은 방식으로 소수를 찾고 있다.

 

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.
2. 2는 소수이다.
3. 2 자기 자신을 제외한 2의 배수는 모두 소수가 아니다.
4. 남아있는 수 가운데 3은 소수이다.
5. 3 자기 자신을 제외한 3의 배수는 모두 소수가 아니다.
6. 남아있는 수 가운데 5는 소수이다.
7. 5 자기 자신을 제외한 5의 배수는 모두 소수가 아니다.
8. 남아있는 수 가운데 7은 소수이다.
9. 자기 자신을 제외한 7의 배수는 모두 소수가 아니다.
10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

 

우선 앞선 방법과 동일하게 판별하고자 하는 수 n이 2 미만인 경우는 당연히 소수가 아니므로 false를 반환해준다. 이후 인덱스 0 ~ n 만큼의 boolean형 배열을 생성한다. 최초에 인덱스별로 할당되는 값들은 false이므로 이 false가 소수를 의미한다고 가정해보자.

 

우선 0과 1은 소수가 아니므로 true를 할당한다. 이후 2부터 검증하는데, 2는 알다시피 소수이다. 따라서 에라토스테네스의 방법대로 2 자기 자신을 제외한 2의 배수는 모두 소수가 아니라고 가정하여 모두 true를 할당한다. 이제 2 이후의 수 중 소수를 찾아 앞선 작업을 동일하게 처리해준다.

 

이러한 방식으로 2부터 순회하면서 특정 i라는 수에 도달 했을 때 i * i의 값이 n을 초과하면 해당 작업을 중단한다. 왜냐하면 소수인지 판별하고자 하는 수가 n인데 n을 초과하는 구간의 수들까지 소수 판별을 할 필요가 없기 때문이다.

 

시간 복잡도 비교

그렇다면 가장 직관적인 방법과 에라토스테네스의 체를 이용한 방법과 둘 중 어느 방법이 시간복잡도 성능이 나을까? 사실 상황에 따라 다르다. 특정한 하나의 수에 대해서만 소수를 판별할 때는 그냥 직관적인 방법을 사용하는 것이 더 빠르다.

 

예를 들어, 2천만이라는 정수에 대해 소수를 판별한다고 가정했을 때 가장 직관적인 방법으로는 10~20ms 정도의 시간이 소요된다. 하지만 에라토스테네스의 체를 이용한 방법을 이용했을 때는 400~600ms 정도의 시간이 소요된다. 이는 에라토스테네스의 체를 이용한 방법의 경우 2 ~ 2천만의 구간 전체에 대해 소수 판별 처리를 진행하기 때문이다.

 

만일 특정 구간의 소수 개수를 구해야 한다면 직관적인 방법 보다는 에라토스테네스의 체를 이용한 방법이 더 나은 성능을 보일 것이다. 예를 들어, 0에서 2천만이라는 구간 내에 있는 소수의 개수를 구한다고 생각해보자. 직관적인 방법으로 수 하나하나 검증하다보면 10초 이상의 시간이 소요되게 된다.