[JAVA] 에라토스테네스의 체 - 소수 구하기

가끔가다 백준이나 프로그래머스 문제를 풀다보면 소수를 구하는 문제가 있는데 그때 사용하면 아주 유용하다! 그렇다면 소수란 무엇인가??

 

소수 (Prime Number) 란 ? : 자신보다 작은 2개의 자연수를 곱해 만들수 없는 1보다 큰 자연수를 말한다. 같은 의미로 1과 자기 자신만을 약수로 갖는 수, 약수를 2개만 갖는 수를 말한다. 예를 들면 2,3,5,7,11,13,,, 등이 있다.

 

그러면 소수를 구하는 알고리즘을 구현하려면 어떻게 해야 할까? 그냥 단순하게, 2와 타깃 숫자 사이의 어떠한 숫자로 나누어 떨어진다면 소수가 아니다. 이걸 코드로 표현한다면 다음과 같다.

 

시간 복잡도 O(n)

private boolean isPrimeNum(int target) {
        for (int i = 2; i < target; i++) {
            if (target % i == 0) {
                return false;
            }
        }
        return true;
    }

그런데 해당 알고리즘은 O(n)의 시간 복잡도를 가진다. 그런데 눈치챘겠지만 사실 2부터 target 숫자까지 모든 숫자로 나눠볼 필요는 없다. 타켓 숫자의 제곱근까지만 확인해 보면 된다. 예를 들어 20의 경우, 4*5 == 5*4 처럼 제곱근을 기준으로 대칭을 이루기 때문이다. 

 

시간 복잡도 O(√n)

private boolean isPrimeNum(int target) {
        for (int i = 2; i <= Math.sqrt(target); i++) {
            if (target % i == 0) {
                return false;
            }
        }
        return true;
}

이런식으로 다시 알고리즘을 구현해 본다면 시간 복잡도를 이전보다 더 줄일 수 있다.

 

그렇다면 왜 에라토스테네스의 체를 왜 사용하는 것일까?? 그냥 제곱근까지만 계산해보면 되는 것이 아닐까? 사실 위의 두 알고리즘은 하나의 target 자연수가 소수인지 아닌지를 판별을 해주는 알고리즘이다. 대량의 소수를 한 번에 판별해야 하는 상황에서 에라토스테네스의 체를 사용하는 것이다.

 

 

에라토스테네스의 체 원리

1. 구하고자 하는 소수의 범위만큼 1차원 배열을 생성한다. 아래의 자료에서는 120이다. 

2. 배열은 2부터 시작하고( 1은 소수가 아니기 때문에 삭제한다. ) 선택한 수의 배수를 모두 삭제한다. 아래 자료의 경우 2의 배수를 제거한다. 

3. 그리고 다음으로 지워지지 않은 수를 선택한다. 즉 3을 선택하고, 선택한 수의 모든 배수를 삭제한다. 이때 이미 지워진 수는 지우지 않으며, 처음으로 선택된 수( 2나 3을 의미 )는 지우지 않는다.

4. 앞의 과정을 배열의 끝까지 반복한다.

3. 배열에 남아있는 모든 수를 출력한다.

 

에라토스테네스의 체 코드

private void isPrimeNum(int target) {
        int[] arr = new int[target + 1];
        for (int i = 2; i <= target; i++) {
            arr[i] = i;
        }
        //에라토스테네스의 체 적용
        for (int i = 2; i <= target; i++) {
            if(arr[i] == 0 ){
                continue;
            }
            for (int j = i + i; j <= target; j += i) {
                arr[j] = 0;
            }
        }
        //최종 적으로 소수 출력하기
        for (int i = 2; i <= target; i++) {
            if (arr[i] != 0) {
                System.out.print(i+" ");
            }
        }
}

 

그렇다면 에라토스테네스의 체를 사용하면 시간 복잡도는?

 

일반적으로 위의 코드에서도 알 수 있듯이 에라토스테네스의 체는 이중 for문으로 구현한다. 그러므로 시간 복잡도가 n^2 정도라도 판단할 수 있다. 그러나 실제 시간 복잡도는 최적화의 정도에 따라 다르겠지만, 일반적으로 O(Nlog(logN))이다. 배수를 삭제하는 연산으로 실제 구현에서 바깥쪽 for문을 생략하는 경우가 빈번하게 발생하기 때문이다. 이러한 이유 때문에 에라토스테네스의 테 기법은 소수를 구하는 일반적인 방법으로 통용된다고 한다. 

 

소수, 에라토스테네스의 체 와 관련된 문제들 (발견하면 계속해서 추가하는중)

 

 

프로그래머스 - 소수 만들기 (https://school.programmers.co.kr/learn/courses/30/lessons/12977#)

프로그래머스 - 소수 찾기 (https://school.programmers.co.kr/learn/courses/30/lessons/12921)

 

 

 

 

 

 

Reference

에라토스테네스의 체

소수 구하기 알고리즘, 에라토스테네스의 체

Sieve of Eratosthenes - Wikipedia