에라토스테네스의 체 (소수 구하기)

이번 시간에는 코딩테스트 준비를 하면서 문제를 풀다가 흥미로운 알고리즘을 발견해서 해당 내용을 포스팅하려고 합니다. 바로바로 '에라토스테네스의 체' 라는건데요. 이번에도 흥미로운 내용이 있으니 한번 둘러보고 가세요!

 

 

에라토스테네스의 체란?

에라토스테네스의 체는 말 그대로 어떤 물질을 걸러주는 '체'를 의미합니다. 여기서는 소수를 걸러주는 체가 되겠네요. 

 

소수에 대해서 아주아주 간단하게 설명하고 넘어가도록 하겠습니다. 

 

소수는 1과 자기자신으로밖에 나눠지지 않는 수를 말합니다. 2 3 5 7 ... 이런 숫자들을 말하죠 

 

1과 자기자신으로밖에 나눠지지 않는 수라는 것은 소수를 공부했던 사람이라면 누구나 떠올릴 수 있는 개념입니다. 

 

이것을 코딩으로 구현하려면 어떻게 해야할까요? 

 

정말 우리가 흔히 알고있는 개념으로 접근하려면 이렇게 해야합니다. 

 

나눠지는 수 ÷ 나누는 수 -> 나머지가 0이면서 나눠지는 수 == 나누는 수 인경우를 체크하면 됩니다. 

 

코드로 구현하면 다음과 같겠죠

 

import java.util.Scanner;

public class Memo {

    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);
        int input = kb.nextInt();

        System.out.println(solution(input));
    }

    private static String solution(int input) {
        String answer = "";

        for (int i = 2; i < input; i++) {
            if (isPrime(i)) {
                answer += i + " ";
            }
        }

        return answer;
    }

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

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

        return true;
    }
}

 

소수의 개수를 찾던간에 직접 찾던간에 2중 for 문을 돌려가면서 찾아야합니다. 하지만 위의 코드는 시간 복잡도가 O(n^2) 으로 값이 조금만 커지면 문제에서 제시하는 시간초안에 해결하지 못해 타임오버가 됩니다. 

 

시간 복잡도에 대한 내용은 이전 포스팅에서 다뤘으니 시간복잡도에 대해서 알고싶으신 분들은 아래의 링크를 확인해주세요.

https://coding-review.tistory.com/267

시간복잡도

 

위의 방식은 정답이긴 하지만 시간초과로 오답이고... 어떻게 해야할까요?

 

바로 나누는 수와 그 배수만큼을 지워버리면 됩니다. 

 

코드로 바로 보시죠

 

import java.util.Scanner;

public class Memo2 {

	/**
     * ex) 입력값이 10이면
     * *초기화
     * 2 3 4 5 6 7 8 9 10
     * 0 0 0 0 0 0 0 0 0
     *
     * * i = 2 일때
     * 2 3 4 5 6 7 8 9 10
     * 1 0 1 0 1 0 1 0 1
     * 2와 2의 배수를 1로 바꾸고 1 증가
     *
     * * i = 3 일때
     * 2 3 4 5 6 7 8 9 10
     * 1 1 1 0 1 0 1 1 1
     * 3과 3의 배수를 1로 바꾸고 1 증가
     *
     * ... 이런식으로 계속 나아가는 방식
     *
     * for (int i = 2 ; i <= n ; i++) {
     *     if (ch[i] == 0) {
     *         answer++;
     *         for (int j = i ; j <= n ; j = j + i) {
     *             ch[j] = 1;
     *         }
     *     }
     * }
     */
     
    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);
        int input = kb.nextInt();

        System.out.println(solution(input));
    }

    private static String solution(int num) {
        String answer = "";
        int cnt = 0;
        int[] arr = new int[num + 1];

        for (int i = 2; i <= num; i++) {
            if (arr[i] == 0) {
                cnt++;
                answer += i + " ";
                for (int j = i; j <= num; j = j + i) {
                    arr[j] = 1;
                }
            }
        }

        return answer;
    }
}

 

주석에도 써있지만 다시 한번 설명하자면

 

예를 들어서 입력값이 10이라고 가정했을 때

 

각각의 숫자를 index로 하는 배열을 만듭니다. 그리고 초기값은 0으로 초기화합니다. 배열의 크기는 입력값 + 1로 설정합니다. 

 

그럼 이런 그림이겠죠

 

0 1 2 3 4 5 6 7 8 9 10 -> index

0 0 0 0 0 0 0 0 0 0 0  -> 실제 값

 

어차피 0 이랑 1은 필요없으니까 빼고 보면

 

↓

2 3 4 5 6 7 8 9 10

0 0 0 0 0 0 0 0 0 

 

현재 인덱스는 2를 가리키고 있습니다. 여기서 인덱스를 1씩 올리면서 값을 확인합니다. 이때 해당 값이 0이면 그 인덱스를 누적합니다. 

 

그리고 그 다음에 2의 배수들을 전부 1로 바꿔줍니다. 

 

2 3 4 5 6 7 8 9 10

1 0 1 0 1 0 1 0 1

 

그리고 인덱스를 하나 증가시킵니다. 

 

   ↓

2 3 4 5 6 7 8 9 10

1 0 1 0 1 0 1 0 1

 

현재 인덱스는 3을 가리키고 있습니다. 해당 인덱스 값이 0이니 값을 누적하고 3의 배수를 전부 1로 바꿉니다. 

 

2 3 4 5 6 7 8 9 10

1 1 1 0 1 0 1 1 1

 

한번만 더해보죠 다음 인덱스는 4를 가리키고 있습니다. 

 

      ↓

2 3 4 5 6 7 8 9 10

1 1 1 0 1 0 1 1 1

 

이번엔 값이 1이네요 그럼 그냥 넘어갑니다. 

 

이런식으로 하나하나 1로 만들다보면 값이 전부 1로 바뀌게 됩니다. 그럼 반복문이 종료됩니다. 

 

이러한 방식을 사용하게 되면 기존에 2중 for 문으로 돌렸을 때의 단점이 완벽히 메꿔집니다. 기존 방식대로였으면 121을 확인하기 위해서는 for 문을 11 * 11 번 즉 121번만큼 돌았어야 했는데 에라토스테네스의 체 알고리즘을 사용하게 되면 인덱스 번호가 11까지만 가도 11의 배수는 전부 사라지기 때문에 121까지 for 문이 가지 않아도 됩니다. 

 

이렇게 소수를 찾아내는 방식이 바로 에라토스테네스의 체 알고리즘 방식입니다. 

 

에라토스테네스의 체 알고리즘을 사용하게 된다면 기존 시간복잡도 O(n^2)에서 O(n^1/2) (n의 제곱근 / 루트 n)으로 확실히 줄일 수 있습니다. 참고로 루트n은 log n과 비슷한 시간복잡도를 갖고있습니다. 그래프 모양에서도 이를 확인할 수 있습니다. 

 

어떤가요? 흥미롭지않나요? 

 

이렇게 공부하고 나니 뭔가... 기분이 오묘하네요. 정말 신기한 광경을 봤을 때의 경외심과 동시에 이걸 모르면 못푼다는 얘기 아닌가? 하는 의구심이 들어서 얼마나 많은 알고리즘을 알아야 하는거지 싶은 걱정도 드네요

 

아무튼 여기까지 '에라토스테네스의 체'에 대해서 알아봤습니다. 

 

긴 글 읽어주셔서 감사합니다. 오늘도 좋은 하루 보내세요~