에라토스테네스의 체

프로그래밍을 꼭 수학을 잘 하는 사람이 해야할 이유는 없지만, 수학을 잘 하는 사람은 코드를 좀 더 효율적으로 짤 수 있단건 여지없는 사실이다. 고대 그리스의 수학자 에라토스테네스는 소수를 찾는 방법을 발견했고, 이 방법이 마치 체로 걸러지듯이 수가 나온다고 하여 에라토스테네스의 체라고 부른다.

에라토스테네스의 체

에라토스테네스의 체 알고리즘은 임의의 자연수 n에 대해 그 이하의 소수를 모두 찾는, 가장 간단하고 빠른 알고리즘이다. 방법을 보면 ‘엥 엄청 무식하게 찾는데?’라고 생각할 수도 있지만, 특정 범위에서 그 범위 내의 모든 소수를 찾아야 하는 경우 소수들간의 연관성(소수를 생성하는 공식)이 나오지 않았으므로 에라토스테네스의 체보다 빠른 방법은 없다.

1부터 100까지의 소수를 찾는다고 생각하고 방법을 설명해보겠다.

1. 1부터 100까지 수를 쓴다

2. 소수, 합성수가 아닌 유일한 자연수 1을 제거한다.

3. 2를 제외한 2의 배수를 제거한다

4. 3을 제외한 3의 배수를 제거한다

5. 5를 제외한 5의 배수를 제거한다 (이 때 4를 제거하지 않는 이유는 2의 배수에서 이미 지워졌기 때문)

6. 7을 제외한 7의 배수를 제거한다

8, 9, 10의 배수들은 모두 위의 과정에서 제거되었다. 이렇게 모두 제거하면 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97이 남는데, 이 녀석들이 100아래의 소수들이다. 에라토스테네스의 체는 특정 범위 내의 소수를 판정하는데 효율적이다 만약 주어진 수 하나가 소수인걸 찾는다면 에라토스테네스의 체보다 소수판정법을 이용하는게 훨씬 빠르다. 또, n보다 작은 어떤수 m이 m = ab라면 a와 b 중 적어도 하나는 $\sqrt n$ 이하이다. 즉 $\sqrt n$이하의 배수만 지우면 에라토스테네스의 체 알고리즘을 효율적으로 이용할 수 있다.