그리스 수학자 에라토스네테스가 고안해 낸 소수를 찾는 알고리즘입니다. 다른 알고리즘에 비해서 논리가 상당이 심플하기 때문에 어렵지 않게 접근할 수 있습니다.
우선 소수의 정의는 1과 자기 자신 외에 약수를 가지지 않는 수 입니다. 따라서 1이 아닌 어떤 수를 n(n > 1)배 했을 때 소수가 나올 수는 없습니다. 이것이 이 알고리즘의 핵심입니다.
소수가 아닌 수는 합성수입니다. 1과 자기 자신 이외에 약수를 가지는 수가 합성수죠.
알고리즘을 간단히 설명하겠습니다. 예를들어 2부터 100까지의 수 중에서 소수를 구한다고 해봅시다. 앞서 예기한 것처럼 1이 아닌 어떤 수(여기서는 2부터 100까지의 수를 차례대로)를 2배, 3배, ... 해서 100을 넘기기 전까지의 배수를 구합니다. (아래 그림)
위 그림과 같이 4, 6, 8, ... 이 숫자들이 되겠죠. 주의할 점은 배수를 할 자기 자신(여기서는 2)은 제외입니다. 이렇게 하면 2라는 녀석은 소수가 될 조건을 만족합니다. 반면에 4, 6 8, 10은 2라는 약수를 공통으로 갖게 되는데 약수를 갖게 되므로 소수에서 탈락입니다. 즉 합성수라는 말이죠.
100까지 이런식으로 탈락 시킬 수들을 걸러놓고 나면 숫자 3에 대해서도 똑같이 해봅시다.
3은 앞에서 걸러진 수가 아닙니다. 따라서 3보다 작은 수 중에 3의 약수가 되는 수는 1외에는 존재하지 않겠죠. 따라서 3은 소수이므로 3을 제외한 3의 배수들을 위와 같은 방법으로 걸러내면 됩니다.
앞에서 걸러낸 수와 겹치는 수도 있고, 어쨌든 또 몇몇 수들이 걸러지겠죠. 100이 넘기 전까지 이작업을 마쳤다면 다음 수 4에 대해서 똑같은 작업을 해야할까요?
그런데 4는 이미 걸러진 수(약수가 있으므로 소수가 아님)이므로 소수가 아닙니다. 4는 이미 약수 2가 있고 4의 배수를 구해서 걸러내는 것은 무의미합니다. 왜냐면 2의 배수들이 4의 배수들을 포함하기 때문이죠. 앞에서 2의 배수들은 이미 걸러졌습니다. 그러므로 넘어가서 5에 대해서 위 작업을 하면 됩니다. 이런 논리로 흰색 칸에 대해서만 위 작업을 해주시면 됩니다.
그래서 다음 6은 건너뛰고 7에 대해서 똑같은 작업을 하고 그 다음은 11에 대해서 하면 됩니다. 이렇게 100까지 하면 걸러진 수들(주황색)을 제외한 10 이하의 수들은 소수가 되는 겁니다.
C코드로 작성해 보겠습니다. 다음은 비주얼 스튜디오 2015에서 작성한 코드입니다.
앞에서 설명한 흰색 칸에 해당하는 수들을 2부터 차례대로 변수 sample에 대입받아 사용할 겁니다. xsample은 sample의 j배를 한 수들을 의미합니다. 중간에 num[xsample]에 false를 대입하는 것은 앞서 그림에서 주황색 칠을 하는 것과 같은 의미입니다.
조건 if(!num[j]) continue; 는 주황색 칠을 했다면 다음 수로 넘어가는 조건문이죠.
사실 소수판별 알고리즘은 수학적으로 어떤 수 n이 있을 때 2부터 √n까지의 수로 차례대로 나누어 딱 떨어지는 수가 없다면 소수임을 판별하기도 합니다. 이런 식으로는 2부터 √n까지 하나씩 다 체크하므로 수가 커질 수록 느려질 수 밖에 없죠.
하지만 에라토스테네스의 체는 앞서 그림같이 소수에 대해서만 배수를 하기 때문에 훨씬 빠릅니다.
그런데 앞에서 언급했듯이 위 코드는 알고리즘의 흐름을 파악하기 위해서 만든 코드로 최적화 작업이 필요합니다. 우선 다음은 1차적인 최적화 작업입니다.
변수 j, sample, xsample 을 하나의 변수 xsample로 해결했습니다. 배수를 저장할 변수 대신 원래의 수를 누적해서 더해줌으로써 해결되었죠.
어쨋든 작은 변화지만 코드는 더 줄었네요.
다음 최적화에 들어가기 전에 몇가지 사항을 알고 있어야 합니다.
i의 값의 범위를 2부터 √n까지만 해도 됩니다.
어떤 수가 소수인지 판별하는 문제는 근본적으로 그 수를 그 수 보다 작은 수들로 나눠봐서 나누어 떨어지는지를 살펴보면 됩니다. 예를들어 97이 소수인지 판별하려면 2로 나누고, 3으로 나누고, 4로나누고, ... 이렇게 96까지 나눠보면 되죠. 그런데 실제로 이렇게 소수를 판별할 때 96까지 할 필요없이 √97까지만 하면 됩니다. (더보기 참고)
마지막으로 xsample의 값을 i*i부터 시작하도록 합니다.
위 알고리즘은 i를 제외한 i의 배수(합성수)를 구해서 배열에서 제외시켜서 소수를 구하는 것이므로 xsample의 값이 i*2, i*3, i*4,...이렇게 증가하게 됩니다. 그런데 i의 값이 5라고 해보면 5*2, 5*3, 5*4,...이렇게 되겠죠? 이 계산은 i의 값이 2일 때, 3일 때, 4일 때 앞에서 이미 했던 계산으로 중복됩니다. 따라서 5*5부터 계산하는 것이 중복도 피하고 효율적이 됩니다.
우선 위 내용을 토대로 다시 코드를 수정해보겠습니다.
두 for문의 내용만 살짝 바뀌었습니다.
이 코드는 더 개선할 수 있는 부분이 있습니다.
2를 제외한 짝수는 모두 합성수이다.
이 사실로 짝수인 경우를 제외하여 검사할 수 있습니다.
이 알고리즘은 N의 값이 커지면 메모리의 사용량도 정비례해서 증가합니다.
앞에서는 num배열의 타입을 bool로 했지만 2^32(2의 32승) =4294967296 인 경우만 해도 4GB의 메모리를 사용하게됩니다. 42억 정도 되는 수를 소인수 분해하는 일은 흔하지 않지만 아무리 그렇다고 하더라도 하나의 수를 소인수 분해하는데 너무 큰 비용이 듭니다.
이에 대한 해결방법으로 비트연산으로 최적화를 할 수 있습니다. 비트연산에 대한 것은 다음 기회에 다루도록 하겠습니다.