에라토스테네스의 체

지금부터 고대로부터 내려오는 유한수 N보다 작은 소수를 나열하는 방법인 에라토스테네스의 체에 대해서 이야기해보겠습니다 에라토스테네스는 기원전 276년에 태어났습니다 그러니까 이 방법은 약 2200년정도 전에 나온거네요 하지만 매우 우아하고 간단해서 아이에게도 쉽게 가르칠 수 있어요 그럼 예를 하나 들어봅시다 100까지의 모든 소수를 계산하고 싶다면 만약 만 또는 10억까지 구하기를 원한다 하더라도 똑같은 방식으로 계산할 겁니다 우선 모든 숫자에 아무런 표시를 하지 않았다고 가정합시다 회색은 아무런 표시가 되지 않았다는 뜻입니다 처음에 1 부터 시작해서 아무런 표시가 되지 않은 수를 만나면 소수입니다 바로 2를 만나고 소수라고 말할 수 있어요 어떤 표시도 없으니까요 두 번째 단계로 2의 배수를 모두 제거합니다 왜냐하면 전부 합성수 이니까요 이렇게 모든 2의 배수를 지울겁니다 빨간색은 합성수입니다 이제 반복합니다 다음은 3으로 넘어가게 되겠네요 3은 아무런 표시가 없으므로 3도 소수입니다 이젠 3의 배수도 지울 수 있습니다 간단한 최적화 방법이 있어요 6은 이미 지워졌습니다 우리는 배수를 지우는 것을 그 숫자의 제곱에서부터 시작하면 간단합니다 그러므로 3의 3배는 9가되고 9부터 시작하여 모든 3의 배수를 합성수라고 표시할 수 있습니다 그러고 나서 다시 돌아가면 4는 건너 뛰어도 되겠네요 4는 이미 표시가 되어있습니다 합성수라는 뜻이죠 다음 5로 넘어가면 아무런 표시가 없으므로 5도 역시 소수입니다 그럼 5에 5배한 값은 25이고 25로가서 25, 30, 35, 40, 45과 같이 5의 배수에 표시를 합니다 전부 합성수입니다 계속해서 7을 만날때까지 계속합시다 7은 아무런 표시가 되어 있지 않으므로 7은 소수입니다 그리고 7의 7배는 49이므로 49부터 시작하여 모든 7의 배수를 합성수라고 표시할게요 다음으로 표시가 안된 11까지 갑시다 11은 소수입니다 11의 11배는 100보다 큰 수입니다 그러므로 이 지점에서 멈출 수 있습니다 사실 10에서 멈출 수도 있었어요 왜냐하면 이제 남아있는 표시되지 않은 수는 전부 소수일 테니까요 그러면 남은 모든 수를 전부 소수라고 표시할 수 있습니다 이게 알고리즘의 전부입니다 매우 간단하지요 그리고 우리가 어떤일을 해야하는지 간단하게 일반화해서 어떠한 숫자 N까지의 모든 소수를 찾는 일종의 체 처럼 작동하는 프로그램을 만들 수 있습니다 먼저 주요 반복문을 만들어보겠습니다 "2부터 N의 제곱근까지의 모든 수 a에 대해" "2부터 N의 제곱근까지의 모든 수 a에 대해" 여기서 알 수 있듯이 10을 만났을때 멈춰야 합니다 방금전에 저는 11까지 셋지만 남은 모든 수가 소수이므로 멈춰야 합니다 그러므로 2에서부터 N의 제곱근까지 다음과 같은 절차를 따를 겁니다 만일 a에 아무런 표시가 되어 있지 않다면 a는 소수라는 것을 알 수 있고 소수를 찾게 된다면 a의 모든 배수들에 대해서 합성수라고 표시를 합니다 이게 끝입니다 그렇게 소수를 찾고 그 배수들에 대해서 표시를 하고 난 다음에는 다시 a보다 1 큰 값으로 돌아가서 다시 시작합니다 2에서 시작하고 다음에 3으로 가고 마찬가지로 4, 5로 갑니다 다 마치고 나면 모든 소수를 구할 수 있습니다 이 또한 반복문으로 이루어져 있습니다 소수를 찾는 주반복문도 있고 또한 그 배수를 지우는 반복문도 있습니다 여기서 중요한 점은 반복문 안에 또 다른 반복문이 있다는 것입니다 반복문 안에 또 다른 반복문이 있다는 것입니다 한 예시로 이 알고리즘으로 프로그램을 만들었습니다 JavaScript로 작성했습니다 만약 100을 넣는다면 그 이하의 모든 소수가 나올 것이고 200을 넣는다면 그 이하의 모든 소수가 850을 넣는다면 850 이하의 모든 소수가 나올 것입니다 이 아래에는 프로그램을 만들 당시의 기록을 첨부하고 어떻게 만들었는지 설명해 놓았습니다