에라토스테네스의 체’

양의 약수를 딱 두 개만 갖는 자연수를 소수라 부른다. 2, 3, 5, 7, 11, …이 그런 수들인데, 인류는 오랜 옛날부터 이런 소수에 대해 관심이 많았다. 소수를 찾아내는 방법은 아주 오래 전부터 알려져 있었는데, 대표적인 것이 ‘에라토스테네스의 체’라는 것이다. 중학교 정도의 교양만 갖추면 대부분 얘기는 들어봤을 테지만, 이번 수학산책에서는 이보다 조금 더 나가보기로 하자.

에라토스테네스의 체란?

에라토스테네스(Eratosthenes, BC 276 경 – 195 경). 그리스의 시인이며, 천문학자며, 지리학자 겸 수학자

에라토스테네스(Eratosthenes, BC 276 경 – 195 경)는 그리스의 시인이며, 천문학자며, 지리학자 겸 수학자다. 지구의 둘레를 상당히 정확한 정도로 맨 처음 잰 사람으로도 유명하다. 자전축이 기울어진 정도 역시 상당히 정확히 측정했다고도 하고, 위도와 경도의 개념을 만들었다고도 한다. 아르키메데스의 유명한 저작, [방법The Method]은 에라토스테네스에게 보낸 서신이었는데, 당대에 자신을 이해해 줄 능력이 있는 사람은 에라토스테네스 뿐이라고 했다고 한다. 에라토스테네스가 수학에 남긴 족적이 하나 더 있는데 바로 ‘에라토스테네스의 체’라고 부르는 소수 생성법이다.

이름이 상징하듯 자연수를 ‘체’로 쳐서 ‘소수’만 골라내는 방법을 제시한 것인데, 방법은 다음과 같다.

1. 먼저 1은 정의상 소수가 아니니까 제외한다. 한 번 체를 친 셈이다. 남은 숫자는 2 이상의 수다. 이 중 가장 작은 수 2는 소수다. 하나 찾아냈다.

2. 방금 찾아낸 소수 2의 배수는 모두 체를 쳐서 거른다. 즉, 짝수를 모두 걸러내 버리고, 홀수 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, … 만 남긴다는 뜻이다. 남은 수 중 가장 작은 수 3은 소수다. 두 번째 소수 3을 찾아냈다.

3. 방금 찾은 소수 3의 배수 역시 모두 거른다. 즉, 3, 6, 9, 12, 15, … 등등을 모두 걸러내 버리자는 뜻이다. (6, 12, 18 등은 이미 걸러냈지만) 그러면 남는 수는 5, 7, 11, 13, 17, 19, 23, 25, 29, … 등이다. 이 중 가장 작은 수 5도 소수다. 세 번째 소수 발견!

4. 방금 찾은 소수 5의 배수도 역시 모두 걸러낸다. 이제 남은 수는 7, 11, 13, 17, 19, 23, 29, … 등이다. 네 번째 소수 7 발견!

5. 방금 찾은 소수 7의 배수도 역시 모두 걸러낸다. 이제 남은 수는 11, 13, 17, 19, 23, 29, 31, … 등이다. 다섯 번째 소수 11 발견!

6. 위와 같은 조작을 반복한다.

특정 숫자 이하의 모든 소수를 찾는 방법 중 이보다 더 단순한 방법은 없을 것 같다. 단순한 방법이지만 의외로 효율이 좋아서, 발견된 지 2000년이 훌쩍 넘은 현재까지도 작은 규모의 소수를 찾는데 제법 애용되는 방법이며, 컴퓨터 프로그래밍의 예제로 단골처럼 등장한다.

소수 세기 함수

에라토스테네스의 체는 소수 세기 함수를 추정하는 데도 상당한 도움을 준다. 소수 세기 함수가 뭐지? 말 그대로 소수가 몇 개인지 세는 함수인데, 조금 더 정확히 말해 보자. 어떤 수 N보다 작거나 같은 소수의 개수를 π(Ν) 이라 쓰고, 이 함수 π를 소수 세기 함수라 부른다. 여기서 π(파이)는 원주율과는 아무 관계가 없고, 소수(primenumber)의 머릿글자 p에 대응하는 그리스 문자를 가져다 쓴 것에 불과하다. 다른 기호를 쓰고 싶지만 워낙 수학계의 관행이니 따르기로 한다.

예를 들어 π(20)은 20보다 작거나 같은 소수의 개수를 말한다. 20 이하의 소수는 2, 3, 5, 7, 11, 13, 17, 19뿐이므로 모두 8개다. 즉 π(20)=8이다. 가만 보면 2이상의 자연수 N이 소수라는 것은 π(N)=π(N-1)+1이라는 얘기와 동일하다. 따라서 어떤 수가 소수냐 아니냐 하는 것과 소수 세기 함수는 밀접한 관련이 있다. 따라서 소수를 알고 싶다는 얘기는 소수 세기 함수를 알고 싶다는 얘기와 본질적으로 같다. 르장드르는 에라토스테네스의 체가 이 소수 세기 함수에 대해 상당한 정보를 준다는 사실을 간파했는데, 간단하게 설명해 보기로 하자.

에라토스테네스의 체: 한 걸음 더 나아가기

에라토스테네스의 체로 몇 차례 거르고 남은 수 중 가장 작은 수가 소수라고 했다. 그런데, 그것만 소수일까? 예를 들어 위에서 5의 배수를 모두 거르고 난 뒤에는 7, 11, 13, 17, 19, 23, 29, … 등이 남았다. 그런데 가만 보면 가장 작은 7만 소수인 게 아니라, 그 뒤로도 한참 동안 소수가 나온다. 실제로 남은 수 중 소수가 아닌 것은 49에서야 맨 처음 나타난다. 이 49의 비밀은 뭘까? 답이 나왔는가? 7의 제곱이다!

한 번 더 예를 들어 보자. 위에서 7의 배수까지 거르고 난 뒤 남는 수 11, 13, 17, 19, 23, 29, 31, …만 보더라도 소수가 상당히 많다. 어디까지 소수임을 확신할 수 있을까? 답이 나왔는가? 7의 배수까지 모두 거르고 남은 수 중 121보다 작은 것은 몽땅 다 소수다!

따라서 단 세 번 거르는 것만으로도 48 이하의 소수를, 단 네 번 거르는 것만으로도 120 이하의 소수는 몽땅 찾을 수 있다. 유식한 표현으로 π(48) , π(120)등을 알 수 있다는 얘기다.

포함-배제의 원리

어떻게 구할 수 있다는 건지, 예를 들어 π(48)을 계산하기로 하자. 2부터 48까지의 수 중 2의 배수, 3의 배수, 5의 배수를 제거하고 남은 것과, 2, 3, 5가 소수라는 사실을 안다. 따라서 일단 48 이하의 수 중 2의 배수나, 3의 배수나, 5의 배수인 것이 몇 개인지 세기로 한다. 흔히 ‘포함-배제의 원리’(inclusion-exclusion principle)라 부르는 방법을 쓰는데, 한두 번쯤 겪었거나 겪을 가능성이 큰 방법이므로 찬찬히 따라가 보자.

1부터 48까지의 자연수 중 n의 배수는 모두 [48/n]개 있다. 여기서 [x]는 x의 정수 부분을 가리키는 기호다. (예를 들어 48/5=9.6이므로 정수부분은 9다) 48 이하의 자연수 중 2의 배수는 모두 24개, 3의 배수는 16개, 5의 배수는 9개다. 따라서 일단 24+16+9 개를 넘지 못한다. 이 중 2x3의 배수 8개, 2x5의 배수 4개, 3x5의 배수 3개는 중복으로 셈했으므로 빼주어야 한다. 반면 2x3x5의 배수 1개는 다시 더해 주어야 한다. 따라서 2 또는 3 또는 5의 배수의 개수는 다음과 같다.

즉, 24+16+9-(8+4+3)+1=35 개다. 따라서 구하고자 하는 값은 다음과 같다.

여기서 마지막에 붙인 식 3-1은 왜 나왔을까? 2, 3, 5는 소수임에도 각각 2, 3, 5의 배수로 셈했기 때문이다. 한편 1은 2, 3, 5의 배수는 아니지만 소수도 아니기 때문에 빼 주어야 하는 것이다. 어쨌든 실제로도 48 이하의 소수는 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 모두 열 다섯 개임을 확인할 수 있을 것이다. 내친 김에 어쩐지 궁금한 π(100)도 계산해 볼 것을 추천한다.

을 계산한 100-50-33-20-14+16+10+7+6+4+2-3-2-1-0+0+4-1=25 개다.

리만 제타 함수 맛보기

하지만, 예를 들어 π(10000)을 구하라고 하면 어떨까? 100 이하의 소수는 25개이므로, 위와 같은 방법을 써서 구하려면 무려 225+2개에 달하는 항이 등장한다. 물론 상당수의 값이 0이므로 실제 계산에 영향을 미치는 항이 줄긴 하지만, 여전히 많은 계산을 요구한다. 따라서 큰 수에 대한 계산법으로는 전혀 적합하지 않다. 여기서 좌절인가…

이쯤에서 정확히 구하려는 생각을 버리고, 조금 타협을 하면 심신이 한결 편해진다. 예를 들어 π(48)을 다시 한 번 구해 보는데, 이번에는 정확히 구하지 않고, 근삿값을 구하기로 하자. 일단 정확한 값은 다음과 같았다.

그런데, [x]의 값은 x와는 잘 해야 1밖에 오차가 안 나는 데다, 그런 오차도 더하고 빼다 보면 상쇄되는 부분도 있을 것이다. 따라서 다음 값과 얼추 비슷할 것이라 추정할 수 있다.

계산이 줄어든 게 하나도 없어 보이지만, 고맙게도 다음처럼 깔끔하게 계산할 수 있다!

실제로 값을 구해 보면, 14.8이므로 원했던 값 15와도 꽤 비슷하다. 마찬가지 방법을 써서

임을 알 수 있다. 내친 김에 다음 계산을 해 보자.

실제로 π(10000)=1229 이므로 상당히 가깝다. 뭔가 그럴 듯 한가?

하지만 이쯤에서 독자 여러분께 주의 및 사과의 말씀을 드려야겠다. 작은 수 48, 100, 10000에 대한 계산만으로 마치 그럴 듯한 만능 방법인 것처럼 현혹했기 때문이다. 불행히도 이 방법은 수가 커지면 잘 안 통한다. [x]와 x 사이의 오차는 1도 안 되지만 워낙 항의 개수가 많은 탓에, 오차가 누적되어 나중에는 무시할 수 없게 커진다. 실제로도 어느 정도 이상의 수에 대해서는 이 방법이 좋지 못한 근삿값을 준다는 게 알려져 있어 대략 낭패다. 소수의 규칙성에 대해 인류가 잘 모른다는 말이 괜히 나온 게 아니구나...

그렇지만 위에서 등장하는 곱셈

및 이를 일반화한 곱셈은 ‘리만 제타 함수’라 부르는 것과 관련되어 있으며, 이 함수는 소수에 대해 상당히 많은 정보를 갖고 있다. 그 얘기는 다음 수학 산책에서 조금 더 하기로 한다.

• 네이버캐스트