알고리즘 :: 최적화된 에라토스테네스의 체

오늘은 코드 전체를 알려드리진 않을 생각입니다. 어차피 여기저기서 쉽게 알 수 있는 유명한 코드이고, 스스로 한 번 생각해 보시라는 의미에서요. 이번 글이 시리니 님의 글과 비교해서 진행 되므로 시리니 님의 글에 나와 있는 코드를 참조하시는 것도 도움이 될 것 같습니다.

에라토스테네스의 체

우선, 시리니 님의 글에 에라토스테네스의 체에 대해 잘 정리 되어있으니 살짝 인용 좀 해볼까요? 좋은 알고리즘을 소개해주시는 시리니 님께 언제나 감사드립니다. ^^

1. 2부터 N까지를 크기로 하는 체(여기서는 배열)를 만든다.
2. 우선 모든 배열 요소를 1로 채운다.
3. 2를 제외한 2의 배수를 체(배열)에서 모두 제거(즉, 해당 배열 요소들을 모두 0으로 설정)한다.
4. 3을 제외한 3의 배수를 … (위 3과 동일)
5. 위의 절차를 N까지 반복해서 그래도 1로 끝까지 버텨낸(?) 배열의 각 인덱스 숫자가 바로 소수다.

간단히 정리해서, 소수와 소수 아닌 수 모두를 체에 담은 후에 소수 아닌 수만 걸러낸다고 보시면 됩니다.

그리고 2번 과정에서 배열 요소를 1로 채운다는 의미는 TRUE로 채운다는 의미입니다. 코드 상에서 조금 더 가독성을 향상시키려면,

typedef enum {FALSE, TRUE} BOOL;

로 미리 선언한 후에 배열을 BOOL형으로 정의합니다. 이렇게 하면 1과 0 대신에 TRUE, FALSE로 이용할 수 있습니다. C++ 에서는 bool형을 직접 지원하는데 위의 BOOL이 4byte인데 비해 bool은 1byte 자료형입니다.

최적화

이제 이 글의 핵심인 최적화 코드에 대해 알아 봐야겠죠?


위 그림은 시리니 님의 글에 소개된 코드에 의한 결과입니다. 쓸데없이 백 만까지 구해봤는데요. 흠… 22초 걸렸네요. 이 시간을 줄이는 게 이 글의 목적입니다.

우선 시리니 님의 글에 소개된 코드 중에서 일부를 보겠습니다.

// i 에 2 배한 값 j 를 i 로 나눠 0 이 되는지 (즉 소수가 아닌지) 보고
// 또 그 j 에 1을 더한 3 을 i 에 곱해서 다시 i 로 나눠 0 이 되는지 보고... (반복)
for (j = 2*i; j <= Num; j++) {
    // 나눠 떨어지는 수가 있다면 그 놈은 이미 소수가 아니다!
    if (j % i == 0) prime[j] = 0;
}

위 코드에 대해서는 주석에 자세히 나와 있습니다(시리니 님 멋있어요^^). 그런데 j++가  눈에 띄네요. 범위가 작다면 문제가 되지 않지만 큰 범위에서는 1씩 더해가며 나눠 떨어지는지 않은지 일일이 비교하는 게 고달프죠. 그러면 어떻게 해야할까요?

어차피 소수로 판정된 수의 배수들은 소수가 아닙니다. 그렇다면 이 배수들만 걸러내주면 알아서 다 정리되겠지요? 아래 코드처럼요.

for(j = i*2; j <= Num; j += i)
{
    prime[j] = FALSE;
}

이미 i가 소수임을 확인한 상태에서 i의 2배수인 j와 그 배수들은 모두 소수가 아닙니다. 그러므로 j++이 아닌 j+=i로 증가문을 지정해주는 것이죠. 그리고 소수인지 아닌지 비교할 필요도 없으므로 바로 소수가 아니라고 FALSE로 알려줍니다.

에이! 이거나 저거나 얼마나 차이 난다고… 하실 것 같아 그 결과를 보여 드리겠습니다.


짜잔! 1초! 와우! GooD! 이 정도면 쓸만하죠?

그런데 사실, 범위가 백 만까지 가서 이런 차이를 보이는 것이지, 그보다 작은 범위에서는 별 차이가 안 납니다. 그리고 연산을 수행한 제 컴퓨터가 팬티엄2라는 것도 고려해야지요. 그렇더라도 이렇게 최적화할 수 있다는 것을 보여줄 수 있기에 전 이 글이 의미 있다고 생각합니다.

음.. 도움 되셨죠? 그래야하는데… ^^;

참고 문헌

범위 내 소수만 걸러내기 (에라토스테네스의 체) :: http://sirini.net/blog/?p=738
알고리즘 :: 소수인지 판별하는 알고리즘을 최적화하자. :: /?p=754