에라토스테네스의 체 소수 찾기를 배우자

에라토스테네스는 그리스의 수학자이자 천문학자 그리고 지리학자이다. 소수를 발견하는 방법으로서 우리는 에라토스테네스의 체를 사용하고 있다. 약수가 1과 자기 자신 딱 두 개만 갖는 자연수를 prime number라고 하는데 prime number를 찾아내는 방법의 대표적인 것이 에라토스테네스의 체이다. 오늘은 중학 수학에서 배우는 소수를 찾는 방법을 알아보자.

 

목차
1. 에라토스테네스는 누구인가?
2. 에라토스테네스 체 소수 찾기
3. 소수 세기 함수
4. 포함 배제의 원리

 

1. 에라토스테네스는 그는 누구인가?

에라토스테네스라는 고대 그리스의 시인이며 천문학자이며 지리학자 겸 수학자이다. 호기심이 많아서 동시에 여러 학문을 공부했으며 해시계로 지구 둘레의 길이를 처음 계산한 업적도 있으며 지리상의 위치를 위도, 경도로 표시한 최초의 학자이기도 하다. 수학에 남긴 족적이 하나 있는데 그것이 바로 에라토스테네스의 체라고 불리는 소수 생성법이다. 여기서 체는 소수만 골라내는 방법을 뜻한다.

2. 에라토스테네스 체를 이용하여 소수를 찾아보자

에라토스테네스 체는 소수를 찾는 방법을 알려주는 것인데 그럼 소수는 어떤 수인지 알아보면 prime number는 약수의 개수가 2개인 자연수 즉 1과 자기 자신만을 약수로 갖는 수를 우리는 prime number라고 한다. 자연수를 '체'에서 찾는 방법을 알아보면, 하나 - 숫자를 차례대로 쓰기, 둘 - 1은 prime number가 아니지 제외, 셋 - prime number 2는 두고 2의 배수 모두 지우기, 넷 - prime number 3은 두고 3의 배수 모두 지우기, 다섯 - 5는 두고 5의 배수 모두 지우기, 여섯- 남은 수는 소수, 지운 수는 합성수, 1은 그냥 자연수 1이다.

3. 소수 세기 함수를 알아보자

에라토스테네스의 체는 소수 세기 함수를 추정하는 데도 사용되고 있는데, 어떤 수 n보다 작거나 같은 소수의 개수를 a라 쓰고 이 함수 a를 prime number 세기 함수라고 한다. 예를 들어 a(10)은 10보다 작거나 같은 prime number의 개수를 말하는데 10 이하의 prime number는 2, 3, 5, 7 이므로 총 4개가 된다. 이것을 수식으로 나타내면 a(10)=4가 되는 것이다.

 

좀 더 알아보면 5의 배수를 지우고 나면 7, 11, 13, 17, 19, 23,... 등 남아 있는데 여기서 가장 작은 수는 7이며 모두 소수로 되어있다가 49에서 prime number가 아닌 수가 처음 시작되는 것을 알 수 있는데 49는 7의 배수임을 알 수 있고 7의 배수를 모두 삭제하고 나면 121보다 작은 수들은 모두 prime number가 된다. 결론적으로 에라토스테네스 체에서 세 번 삭제하면 48 이하의 소수만 남고 네 번 삭제하면 120 이하의 prime number만 남는 것을 알 수 있다.

4. 포함-배제의 원리를 살펴보자

2부터 48까지 수 중에 2의 배수와 3의 배수 그리고 5의 배수를 삭제하고 남은 수는 2, 3, 5가 소수라는 것을 알 수 있으며 여기서 2의 배수와 3의 배수 그리고 5의 배수가 몇 개인지를 알아보기 위해서 필요한 것이 포함 배제의 원리인 것이다. 1부터 48까지의 자연수 중 n의 배수는 48 나누기 n으로 하면 몇 개 인지 알 수 있다. 이공식으로 2의 배수의 개수를 알아보면 48 나누기 2는 24개, 3의 배수는 48 나누기 3은 16개, 5의 배수는 48 나누기 5는 9 나머지 3인데 여기서 몫만 보면 되기에 9개가 된다. 이렇게 포함 배제의 원리로 해당 수의 배수가 몇 개인지 알 수 있다.