최근 수정 시각 : 2019-08-08 12:14:44

에라토스테네스의 체

파일:attachment/Erathosthenes_sieve.png
1. 개요2. 방법3. 여담4. 관련 문서

1. 개요

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

2. 방법

소수를 찾는 가장 간단한 방법이자 가장 무식한 방법이다. 그 방법은 다름아닌 직접 나누기. 예를 들어 1~50까지의 소수를 찾는다 하자.
일단 1부터 50까지 숫자를 쭉 쓴다.
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
일단 1을 지우자.(1은 소수도, 합성수도 아니며, 기초수라고 해서 별도로 분류한다.)
2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
2를 제외한 2의 배수를 지우자.
2 3 5 7 9
11 13 15 17 19
21 23 25 27 29
31 33 35 37 39
41 43 45 47 49

뭔가 많이 줄어든 것 같은데 이거 맞다.
3을 제외한 3의 배수를 지우자.
2 3 5 7
11 13 17 19
23 25 29
31 35 37
41 43 47 49
4의 배수는 지울 필요 없다.(2의 배수에서 이미 지워졌다.) 2,3 다음으로 남아있는 가장 작은 수, 즉 5의 배수를 5를 제외하고 지우자.
그리고 마지막으로 7의 배수까지 지워제끼면,[1]
2 3 5 7
11 13 17 19
23 29
31 37
41 43 47

이런 식으로 남은 것들의 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의 배수...쭉쭉 나누는 것이다.

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

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

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

3. 여담

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

리만 가설 문서를 참고하면 좋다.

4. 관련 문서



[1] 50의 제곱근이 7이상 8 미만이다.[2] 사실 없진 않다. 근데 너무 비효율적이라(...)

분류