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

2009/02/23 12:00

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

에라토스테네스의 체

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

  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
알고리즘 :: 소수인지 판별하는 알고리즘을 최적화하자. :: http://hisjournal.net/blog/128
크리에이티브 커먼즈 라이센스
Creative Commons License

6l4ck3y3 0x07 알고리즘 , , , , , ,

Trackback Address:이 글에는 트랙백을 보낼 수 없습니다
  1. 앗.. 저건 그 전설의 소(솟)수 계산해내는 방식....
    이세상에 수열중에서 "소(발음 : 솟)수의 수열"만이
    증명(일반항 구하는 공식)이 안되고 있죠..

  2. Blog Icon
    아리새의펜촉

    에라토스테네스 할부지가 아니었으면 과연 지금도 소수를 계산할 수 있을지... 한 명의 천재가 세상을 바꾼다는 게 맞는 말 같아요. 언젠가는 또 다른 천재가 소수의 일반항 공식을 만들지도요.

  3. 안녕하세요 :$

    위의 코드에서 조금[?] 더 개선할 방법을 끄적이자면,

    ## for(j = i*2; j <= Num; j += i)

    j의 초기값을 i*i 로 계산해도 올바른 답을 구할 수 있습니다. (주의하셔야 할 점은, i*i 가 integer 값을 넘어서는 경우인데, 이는 i의 max를 sqrt(Num) 까지만 수행되도록 해주면 해결됩니다.)

    초기값을 i*i 로 두어도 되는 이유는, ' for j ' 가 하는 역할이 소수 i의 배수를 체크하는 것인데, "i*i 보다 작은 수" 중 "i의 배수"는 이미 체크되어있기 때문이지요.

  4. Blog Icon
    아리새의펜촉

    말씀하신 대로 j의 초기값을 i의 제곱으로 두었더니 백만까지 검출하는데 1초도 걸리지 않네요. i의 max 값은 이미 limit로 구현했기 때문에 따로 할 필요까지는 없을 것 같구요.

    알려주셔서 정말 고맙습니다.