요약
에라토스테네스 체는 각 수의 배수를 지워가며 소수를 찾아내는 알고리즘이다.
- 구하고자 하는 소수의 범위 만큼 1차원 배열을 생성한다.
- 2부터 시작하여 현재 숫자가 지워지지 않을 때 해당 숫자의 배수에 해당 하는 수를 배열에서 끝까지 탐색하며 지운다. 이때 처음으로 선택된 숫자는 지우지 않는다.
- 배열의 끝까지
2번을 반복한 후 남아 있는 수를 모두 출력한다.
이론
소수란?
소수는 자신보다 작은 2개의 자연수를 곱해 만들 수 없는 1보다 큰 자연수를 말한다.
이와 같은 의미로 1과 자기 자신 외에 약수가 존재하지 않는 수를 말한다.
또한 소수는 해당 범위 값에 루트 값 범위 까지만 조사하면 약수가 존재한지 아닌지로 판별이 가능하다.
왜냐하면
첫번째, 자연수 A는 (루트A x 루트A)값이 되기 때문이다.
두번째, 자연수 A는 두개의 약수를 곱해야 A가 된다.
이 두가지로 다음과 같은 결론을 만들 수 있다.
정수 A의 약수 a, b가 A의 딱 절반 값이라면 두 약수는 모두 루트 A가 된다.
여기서 약수 a가 루트 A보다 큰 값을 가지게 된다면 약수 b는 루트 A보다 작아지게 된다.
이걸 이용해서 소수 판별은 좀 더 좁은 범위에서 실행 할 수 있다
코딩 테스트에서는 이러한 소수를 판별하는 방식을 묻는 소수 구하기 문제가 종종 출제된다.
에라토스테네스 체 원리
소수를 구하는 방법은 for문, 재귀 함수 등 다양한 방법이 있지만 코딩 테스트에서 대표적인 판별법으로는 에라토스테네스의 체 원리가 있다.
에라토스테네스의 체 원리는 다음과 같다.
- 구하고자 하는 소수의 범위 만큼 1차원 배열을 생성한다.
- 2부터 시작하여 현재 숫자가 지워지지 않을 때 해당 숫자의 배수에 해당 하는 수를 배열에서 끝까지 탐색하며 지운다. 이때 처음으로 선택된 숫자는 지우지 않는다.
- 배열의 끝까지
2번을 반복한 후 남아 있는 수를 모두 출력한다.
이해하기
1부터 20까지의 수 중 소수를 구하는 예시를 보면서 에라토스테네스의 체의 원리를 알아보자
구하고자 하는 소수의 범위 만큼 1차원 배열을 생성한다.
먼저 주어진 범위까지 배열을 생성한다. 이후 1은 소수가 아니므로 0으로 바꾸자
2부터 시작하여 현재 숫자가 지워지지 않을 때 해당 숫자의 배수에 해당 하는 수를 배열에서 끝까지 탐색하며 0으로 바꾸거나 지운다. 이때 처음으로 선택된 숫자는 지우지 않는다.
예를들어 숫자 2는 0이 아니므로 숫자 2가 선택된다.
이후 선택한 수 2의 배수를 모두 삭제하거나 0 으로 바꾼다.
선택한 수 다음으로 0이 아니거나 지워지지 않는 수를 선택한다.
즉, 3을 선택하고 선택한 수의 배수를 모두 0으로 바꾸거나 삭제한다.
위 과정을 소수 범위 까지 반복한 후 삭제되지 않은 수를 모두 출력한다.
시간복잡도
일반적으로 에라토스테네스의체를 구현하려면 이중 for문을 이용하므로 시간 복잡도가 O(N) 정도라고 판단할 수 잇다. 하지만 실제 시간 복잡도는 최적화의 정도에 따라 다르겠지만, O(Nlog(logN)이다.
그 이유는 배수를 삭제하는 연산이 바깥쪽 for문 조건에 의해 생략하는 경우가 빈번하게 발생하기 때문이다. 이러한 이유 때문에 에라토스테네스의 체 기법은 현제에도 코딩 테스트에서 소수를 구하는 일반적인 방법으로 통용되고 있다.
