에라토스테네스의 체가 과연 빠르긴 빠르네

꼭 이런 짓을 하고싶을 때가 있다.
소수의 합을 구할 때 에라토스테네스의 체가 빠르다는 거 당연한데, 굳이 일일이 계산하는 거랑 비교해보고 싶었다.
왜 그런지 따윈 없고... 단지 있다면 얼마 전 모 블로그에 내가 쓴 답글이 신경쓰여서랄까나...

그래서 VS .Net 2003으로 만들어봤다.

#include "stdafx.h"
#include <memory.h>
#include <math.h>
#include <windows.h>

#define PRIMES 2000000

int is_prime(int a)
{
    int i, sqrn=(int)sqrt((double)a);

    for(i=3; i<=sqrn; i+=2)
        if(a%i==0)
            return 0;
    return 1;
}

void brutal(int &iPrimes, long long &lSum)
{
    int i;
    lSum=2;
    iPrimes=1;

    for(i=3; i<PRIMES; i+=2)
    {
        if(is_prime(i))
        {
            iPrimes++;
            lSum+=i;
        }
    }
}

void eratosthenes(int &iPrimes, long long &lSum)
{
    bool *bNoPrime = new bool[PRIMES];
    lSum = 0;
    iPrimes = 0;
    int iMaxCompare = (int)sqrt((double)PRIMES);

    memset(bNoPrime, 0, sizeof(bool)*PRIMES);

    int i;
    for (i=2; i<=iMaxCompare; i++)
    {
        if (!bNoPrime[i])
        {
            iPrimes++;
            lSum += i;
        }

        for (int j=i*i; j<PRIMES; j+=i) bNoPrime[j] = true;
    }

    for (i=iMaxCompare+1; i<PRIMES; i++)
    {
        if (!bNoPrime[i])
        {
            iPrimes++;
            lSum += i;
        }
    }

    delete bNoPrime;
}

int main(int argc, char* argv[])
{
    DWORD dw;

    int iPrimes;
    long long lSum;

    dw = GetTickCount();
    eratosthenes(iPrimes, lSum);
    dw = GetTickCount()-dw;

    printf("Sieve of eratosthenes method\n  : %d prime numbers, sum is %I64d (%u milisec)\n", iPrimes, lSum, dw);

    dw = GetTickCount();
    Sleep(100);
    brutal(iPrimes, lSum);
    dw = GetTickCount()-dw;
    printf("Brutal force method\n  : %d prime numbers, sum is %I64d (%u milisec)\n", iPrimes, lSum, dw);

    return 0;
}

결과는 당연히 에라토스테네스의 체 쪽이 훨씬 빠르다.

Sieve of eratosthenes method
  : 148933 prime numbers, sum is 142913828922 (31 milisec)
Brutal force method
  : 148933 prime numbers, sum is 142913828922 (469 milisec)

이걸 해보며 발견한 시궁창같은 현실.

1. Visual C++ 6.0은 long long 형도 인식하지 못한다. 얜 정말 안 되는 애다.
첨엔 결과가 무식하게 클 줄 알고 long long으로 정의했는데, long long을 인식못하는 걸 보고 걍 .Net 2003으로 변절.
__int64로 바꾸면 되긴 하지만, 이미 난 삐졌음!
그런데, 결과는 long int 범위 안쪽. OTL

2. VS 계열에선 bool은 내부적으로 1바이트를 사용하고, BOOL(==int)은 4바이트를 사용한다.
따라서 BOOL이 훨씬 빠른 것이 상식이다.
(32비트 CPU에겐 32비트 연산이 가장 빠름, 8비트는 32비트로 확장해서 처리)
그런데, 소수 테이블을 bool로 지정할 때가 BOOL로 지정할 때보다 훨씬 빠르다. 뭐지?

3. VS6이나 VS.Net 2003이나 2백만 개의 배열은 못 잡는다. 런타임 오류 발생.
그래도 new를 이용해 동적으로 할당받는 건 문제가 없으니 예쁘게 봐주고 넘어감.

4. 댓글 보고 다시 확인해보니 결과가 틀렸음. long이 아니라 long long이 맞음.
그런데 잘못 생각한 이유는 다름아닌 .Net 2003의 printf에서 "%lld"를 인식하지 못하기 때문.
MSDN을 뒤져보니 VS2005부터는 %lld를 인식하나보다. 제길슨.

참, 무식하게 찾는 쪽 코드는 Studying the Logical World에서 거의 그대로 업어왔다.
여기가 앞에서 언급한 그 블로그다.