최근 수정 시각 : 2020-03-09 16:29:46

에라토스테네스의 체

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

1. 개요

고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법. 이 방법은 마치 로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체'라고 부른다. 따지고 보면 [math(f \left(x\right) = x \, \bold{1}_{\mathbb{P}}\left(x\right))][1]의 수열 중 0이 아닌 것을 표로 시각화한 것이라고 볼 수 있다.

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]) 2,3 다음으로 남아있는 가장 작은 수, 즉 5의 배수를 5를 제외하고 지우자.
그리고 마지막으로 7의 배수까지 지워제끼면,[3]
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과 합성수를 지우면 당연히 나머지가 남는다(...)

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

한편, 에라토스테네스의 체를 이용해 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. 여담

마지막 구호 생략 항목에 의하면, 에라토스테네스의 체를 머릿속에서 즉각적으로 실행해야 하는 '소수 생략'이라는 가히 정신나간 지시를 했다는 증언이 있다.

일종의 노가다 방식이라 상당히 무식한 방법이긴 하지만, 개념 자체는 간단한 데다 프로그래밍에서는 반대로 상당히 효율적인 방법이 된다. 프로그래밍에서 순수한 노가다로 소수를 찾을 경우 2를 넘는 모든 홀수가 약수가 있는지 싹 다 검사해야 하고 이 과정이 엄청나게 오래 걸린다.[5] 코딩테스트 같은 곳에서 이런 무식한 방법을 썼다간 절반도 못 가고 실행시간 초과로 0점 맞을 수준. 하지만 에라토스테네스의 체는 반대로 2부터 배수들을 지워나가는 방식이기 때문에 숫자마다 일일이 약수가 있는지 검사할 필요가 전혀 없고, 이미 지워진 숫자는 바로 건너뛰면 되니 실행시간이 급감한다. 특히 특정 범위가 주어지고 그 범위 내의 모든 소수를 찾아야 하는 경우[6] 에라토스테네스의 체보다 빠른 방법이 없다. 프로그래밍에도 수학적 지식이 필요하다는 걸 일깨워주는 좋은 예시.

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

4. 관련 문서



[1] [math(\bold{1}_{\mathbb{P}}\left(x\right))]는 [math(x)]가 소수이면 1, 그렇지 않을 경우 0의 값을 띠는 판별 함수이다.[2] 4의 케이스만 봐도 알 수 있겠지만, 이미 지워진 수는 모든 배수가 앞선 케이스에서 지워졌기 때문에 검사할 필요 없이 그냥 패스하면 된다. 즉 검사 범위가 커지면 커질수록 지워지는 숫자가 많아지기 때문에 검사 횟수가 줄어든다.[3] [math(7 < \sqrt{50} < 8)]이므로.[4] 사실 없진 않다. 근데 너무 비효율적이라(...)[5] 예를 들어 97이 소수인지를 프로그래밍으로 검사할 경우, 프로그래밍에서는 간단하게 찾을 방법이 없기 때문에 97의 제곱근 이하 정수 중 가장 큰 수인 9부터 2까지 각 수로 97을 한 번씩 다 나눠봐야 한다. 즉 97 하나 검사하는 데에 나눗셈 연산을 8번이나 해야 한다. 이걸 1000 이하 모든 정수에 적용했다간...[6] 예를 들어 정수 N이 주어지고 N 이하의 모든 정수를 검사해야 하는 경우. 이런 식의 문제에서 N은 다섯 자리 이상을 훌쩍 넘어가기도 하기 때문에 이런 단축 방법을 모르면 답이 없다.

분류