기존 알고리즘 포스트는 Javascript 언어로 구현됐었는데요. 이번 포스트부터는 Java 언어로 구현됩니다.

기존의 소수 찾기 알고리즘

기존의 소수 찾기 알고리즘은 다음과 같은 형태로 진행됩니다.

1. 숫자 n에 대하여 2부터 √n까지 나누어 떨어지는 수가 있는지 확인
2. 만약 나누어 떨어지는 수가 존재하면 소수 X
3. 1번과 2번 과정을 2부터 n까지 반복하면 1부터 n까지의 수 중 소수를 찾아낼 수 있음.

√n까지만 확인하는 이유는 n이 a*b로 나누어 떨어질 때 a, b 둘 중 하나는 √n 이하의 수가 됩니다.
ex) 144 = 12 * 12 (√144 = 12), 50 = 2 * 25 or 5 * 10 (√50=7.071)

그렇기에 √n까지만 계산하는 경우에도 약수가 존재하는지 확인할 수 있습니다.

따라서 위 과정에 의해 소수 찾기 알고리즘을 구현하면 다음과 같이 간단한 코드를 얻을 수 있습니다.

public class Prime {

    public static boolean isPrime(int n) {
    	//1은 소수가 아니므로 false
        if (n < 2) {
        	return false;
        }
        
        //2 이상의 수에 대해서는 2부터 √n까지 나누기를 반복
        for (int i = 2; i <= Math.sqrt(n); i++) {
        	//나누어 떨어지는 경우가 있으면 소수가 아니므로 false
            if (n % i == 0) {
            	return false;
            }
        }
        
        return true;
    }
}

이 알고리즘은 정말 단순하고 직관적인 구조를 가지고 있으나 숫자 하나에 대해 2부터 √n의 모든 경우를 나누게 되기 때문에 1부터 n까지의 수 중 모든 소수를 찾는 경우 시간 복잡도가 O(n√n)으로 n이 커질수록 기하급수적으로 오랜 시간이 걸리게 됩니다.

---

에라스토테네스의 체

고대 그리스의 수학자 에라스토테네스가 고안한 수를 걸러내는 방식으로 빠르게 소수를 찾는 방법을 에라스토테네스의 체라고 부릅니다.

그리고 이 방식을 구현한다면 위에서 소개한 브루트-포스 방식의 소수찾기보다 더 빠르게 소수를 찾아낼 수 있습니다.

에라스토테네스의 체의 원리는 다음과 같습니다.
1. 1을 제거한다.
2. 2를 제외한 2의 배수들을 모두 제거한다.
3. 3을 제외한 3의 배수들을 모두 제거한다.
4. 4는 2의 배수를 제거하는 과정에서 4포함 4의 배수들이 지워졌으니 다음 수로 넘어간다.
5. 5를 제외한 모든 5의 배수들을 제거한다.
6. 위와 같은 원리를 적용해서 √n까지 반복한다.

위와같은 과정을 거치면 1부터 n까지의 모든 소수를 가장 빠르게 찾을 수 있는 방법이 됩니다. 시간복잡도도 O(N log log N)이기 때문에 기존 방식보다 훨씬 빠름을 알 수 있죠.

public class SieveOfEratosthenes {

    public static boolean[] getPrimes(int n) {
        boolean[] isPrime = new boolean[n + 1];	//0 ~ n까지 저장해야하므로 배열 크기는 n + 1
        Arrays.fill(isPrime, true);  // 처음엔 모두 소수(true)로 가정
        isPrime[0] = isPrime[1] = false;  // 0과 1은 소수가 아님

		//√n까지 검사 반복
        for (int i = 2; i * i <= n; i++) {
            if (isPrime[i]) {
                // i의 배수를 모두 지움
                for (int j = i * i; j <= n; j += i) {
                    isPrime[j] = false;
                }
            }
        }

        return isPrime;
    }
}

√n까지 검사 반복을 수행하는 for문의 조건식이 i * i <= n인데요.

i <= Math.sqrt(n)를 사용하는 경우와 비교하면 매 반복마다 Math.sqrt(n)를 호출해야하며, 부동소수점 연산이 발생하기 때문에 효율이 나빠지게 되므로 더 빠른 연산을 위해 조건식을 i * i <= n으로 작성하게 되었습니다.

---

마지막으로 주의해야할 점이 하나 있는데요. 에라스토테네스의 체는 1부터 n까지의 모든 소수를 찾는 연산에 적합합니다.

단순히 n이 소수인지 판별하는 문제에서는 처음 방식이 오히려 더 좋은 효율을 보여준다는 것에 주의해주세요. (에라스토테네스의 체는 √n까지의 배수를 제거하고 찾으므로 더 느림!!!)