[알고리즘] 백준 1929 소수 구하기 - 에라토스테네스의 체

문제 본문

 

소수는 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수입니다. 대표적으로 2, 3, 5, 7.. 등등이 있습니다.

단순 소수 찾기 - O(n^2)

  public static boolean isPrime(int num) {
     if (num == 1) return false;

     for (int n = 2; n < num; n++) {
        if (num % n == 0 ) {
            return false;
         }
     }

     return true;
  }

가장 간단하게 소수를 구하는 방법은 1을 제외하고 자신보다 작은 자연수로 나누어 나머지가 0이 나오는 지 확인하는 것입니다.
하지만 위 방법은 O(n^2)의 시간 복잡도를 가져서 num의 값이 크다면 시간초과를 발생합니다.

제곱근을 활용하여 소수 찾기 - O(nlogn)

 public static boolean isPrime(int number) {
        if (number == 1) {
            return false;
        }
        for (int n = 2; n <= (int) Math.sqrt(number); n++) {
            if (number % n == 0) {
                return false;
            }
        }
        return true;
    }

사실 n이 소수인 것을 증명하기 위해 n - 1의 수까지 일일이 비교할 필요가 없습니다.
예를 들어 144인 수는 12의 제곱입니다. a1 x a2의 수식으로 표현하면 12 x 12라고 할수 있겠죠? 그렇다면 12보다 큰 수로 144을 나눴을 때 나머지가 0이 나오는 수식이 존재할까요? 없습니다!

144의 결과를 나타내는 다른 수식을 봐도 24 x 6, a1은 증가했지만 a2는 감소했습니다. 즉 12보다 큰 수로 나누어 나머지가 0이 나온다고 해도 그 수는 12보다 작은 자연수로 곱한 셈이 되는 것으로 2부터 제곱근까지 비교하면 되는 것입니다.

위 방법으로 해당 문제가 풀리긴 하지만 더 시간을 절약하는 방법이 있습니다.

에라토스테네스의 체 - O(nloglogn)

    public static void eratos(int start, int end) {
        boolean[] ranges = new boolean[end]; //기본값 false
        ranges[0] = true; //1은 제외

        for (int t = 2; t * t <= end; t++) {
            if (ranges[t - 1]) {
                continue;
            }
            for (int i = t + t; i <= end; i += t) {
                if (i % t == 0) {
                    ranges[i - 1] = true;
                }
            }
        }

        for (int t = start - 1; t < ranges.length; t++) {
            if (!ranges[t]) {
                System.out.println(t + 1);
            }
        }
    }

에라토스테네스의 체는 1을 제외한 자연수부터 시작하여 자신의 배수에 해당하는 숫자들을 하나씩 지워가며 소수를 남겨두는 방식입니다.
참고 링크를 들어가면 그림으로 잘 설명되어 있습니다.

제곱근을 활용하여 소수 찾는 방법의 이론도 같이 사용되었습니다. 따라서 시간 복잡도가 훨씬 줄어듭니다!

 

 

참고

• 에라토스테네스의 체