에라토스테네스의 체

고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법. 이 방법은 마치 로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체'라고 부른다.

소수를 찾는 가장 간단한 방법이자 가장 무식한미개한 방법이다. 그 방법은 다름아닌 직접 나누기. 예를 들어 1~50까지의 소수를 찾는다 하자.

일단 1부터 50까지 숫자를 쭉 쓴다.
12345678910
11121314151617181920
21222324252627282930
31323334353637383940
41424344454647484950
일단 1을 지우자.(1은 소수도, 합성수도 아니며, 기초수라고 해서 별도로 분류한다.)
2345678910
11121314151617181920
21222324252627282930
31323334353637383940
41424344454647484950
2를 제외한 2의 배수를 지우자.
23579
1113151719
2123252729
3133353739
4143454749

뭔가 많이 줄어든 것 같은데 이거 맞다.

3을 제외한 3의 배수를 지우자.
2357
11131719
232529
313537
41434749
4의 배수는 지울 필요 없다.(2의 배수에서 이미 지워졌다.) 2,3 다음으로 남아있는 가장 작은 수, 즉 5의 배수를 5를 제외하고 지우자.

그리고 마지막으로 7의 배수까지 지워제끼면,[1]

2357
11131719
2329
3137
414347

이런 식으로 남은 것들의 2배수, 3배수,...n배수를 지우다보면 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47이 남는다. 이것이 50미만의 소수이다.

이런 방법으로 만약 n이하의 소수를 모두찾고 싶다 하면 1부터 n까지 쭉 나열한 다음에(...) 2의 배수, 3의 배수, 5의 배수...쭉쭉 나누는 것이다.

사실 소수를 '찾는 방법'이라기엔 좀 뭐한게... 합성수를 지우면 당연히 나머지가 남는다(...)

아직까지 소수들 간의 연관성(=소수를 생성할 수 있는 공식)이 나오지 않았으므로[2], 소수를 찾고싶으면 그냥 노가다로 나눠보든가 해야한다.

한편, 에라토스테네스의 체를 이용해 1~n까지의 소수를 알고 싶다면, n까지 모든 수의 배수를 다 나눠 볼 필요는 없다. 만약 어떤 수 [math]m=ab[/math]라면 [math]a[/math][math]b[/math] 중 적어도 하나는 [math]\sqrt{n}[/math]이하이다. 즉 n보다 작은 합성수 m은 [math]\sqrt{n}[/math]보다 작은 수의 배수만 체크해도 전부 지워진다는 의미이므로, [math]\sqrt{n}[/math]이하의 수의 배수만 지우면 된다. 단적으로 1~50인 위의 경우, 사실은 7의 배수 중 남아있는 49 하나만 더 지우면 끝난다.

마지막 구호 생략과 어쩐지 관련있을지도 모른다 (?)

리만 가설 문서를 참고하면 좋다.
  1. 50의 제곱근이 7이상 8 미만이다.
  2. 사실 없진 않다. 근데 너무 비효율적이라(...)