[Algorithm] 에라토스테네스의 체

알고리즘에 대한 이해 !

에라토스테네스의 체란 소수를 판별하는 알고리즘입니다 !

소수를 대량으로 빠르고 정확하게 구하는 방법입니다.

소수란 무엇인가 ?

소수는 양의 약수를 두 개만 가지는 자연수, 즉 1과 자기자신으로만 나누어지는 수를 의미합니다.

2, 3, 5, 7, 11 ...등이 있죠 !

반복문을 통해 소수를 구하는 법을 먼저 확인하겠습니다 !

private boolean isPrimeNumber(int targetNumber) {
      for(int i = 2 ; i < targetNumber; i++){
                      //자기 자신 의외의 숫자로 나누어 떨어지면 false(소수 아님)
          if(targetNumber % i == 0 ) {
              return false;
          }
      }
      return true;
 }

위와 같이 알고리즘을 작성하는 경우 소수 판별 알고리즘의 시간 복잡도는 O(N)입니다.

즉 ! 모든 경우의 수를 다 확인하여 약수 여부를 확인한다는 점에서 몹시 비효율적이라고 볼 수 있죠 !

에라토스테네스의 체 구현방법 !

O(N)의 시간 복잡도를 O(N^(1/2))로 빠르게 연산할 수 있습니다.

아래의 이미지를 보면서 설명해드리겠습니다 :)

  1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.

  2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)

  3. 자기 자신을 제외한 2의 배수를 모두 지운다.

  4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)

  5. 자기 자신을 제외한 3의 배수를 모두 지운다.

  6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)

  7. 자기 자신을 제외한 5의 배수를 모두 지운다.

  8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)

  9. 자기 자신을 제외한 7의 배수를 모두 지운다.

  10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다. (보라색)

에라토스테네스의 체 구현하기 !

매개변수로 전달받은 n까지의 소수의 수를 구하기 위해서 check라는 확인 배열을 n+1로 생성해줍니다 ! (n번 인덱스까지 구하기 위해)

0, 1은 소수에 포함이 되지 않기 때문에 반복문은 2부터 시작을 해 n까지 설정을 해줍니다.

check배열에 i번 인덱스가 0일 때는 소수로 판별되기 때문에 answer 값을 증가시켜주고, 이후 반복문을 통해 i의 배수의 인덱스에 모두 1로 체크를 해줍니다. 여기서 중요한건 i의 배수 값만 체크해야되기 때문에 증가하는 값이 'j++'이 아니라 'j += i'로 설정해줘야된다는 점 ! 

이렇게 어렵지 않게 구현할 수 있습니다 ! 화이팅 !

public static int solution(int n ){
        int answer = 0;

        int[] check = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            if (check[i] == 0){
                answer++;
                for (int j = i; j <= n; j = j + i) {
                    check[j] = 1;
                }
            }
        }

        return answer;
    }