50. 프로젝트 오일러 #50 : 이어지는 소수들의 합

이번 문제는 난이도 자체는 그리 어렵지 않습니다.  프로젝트 오일러 사이트에서 주어진 난이도는 5%입니다.

저에게 있어서 이 문제 자체가 어렵다는 생각은 하지 않았습니다.  하지만 속도를 빠르게 하려다보니 많은 생각을 해야만 했습니다.

문제는 주어진 범위안의 연속된 소수의 합이 또다른 소수가 될 때, 주어진 범위안의 소수 갯수가 최대가 되는 소수를 찾는 것입니다.

처음에 도전한 방법은 단순무식한 방법이었습니다.  단순무식한 방법이라고 하지만, 나름대로 속도를 빨리 나오게 하려고 노력하였습니다.

아래 소스는 단순무식한 방법으로 짰을 때입니다.

#define LIMIT   1000000

void solve1()
{
    static unsigned primes[LIMIT/2];
    unsigned pcount = 0;

    primes[pcount++] = 2;
    primes[pcount++] = 3;

    for( unsigned p = 5 ; p < LIMIT ; p += 2 )
    {
        bool isPrime = true;
        for( int i = 1 ; primes[i]*primes[i] <= p ; i++ )
            if( p%primes[i] == 0 ) { isPrime = false; break; }
        if( isPrime ) primes[pcount++] = p;
    }
    int max = 1, maxv = 2;
    for( int i = 1 ; i < pcount ; i++ )
    {
        for( int j = 0 ; j < i-max ; j++ )
        {
            int sum = 0, k;
            for( k = 0 ; sum < primes[i] ; k++ ) sum += primes[j+k];
            if( sum == primes[i] && max < k ) { max = k; maxv = primes[i]; }
        }
    }
    printf("ans = %d(%d)\n", maxv, max);
}

시간이 너무 많이 걸려서, 좀 더 빠르게 하려고 알고리즘의 전체 골격을 뜯어고치지는 않고, 속도를 개선할 수 있는 방법을 생각했습니다.  연속된 소수의 합이기 때문에 미리 합을 구해서 저장하면 속도를 개선할 수 있을거라 생각했습니다.

그런데, 여러가지 문제가 생겼습니다.  소수들의 합을 첫번째부터 현재것까지 저장하다보니, 32비트 정수형 변수로는 할 수가 없었습니다.  그래서 64비트로 소수들의 누적합을 저장합니다.

그래서 짜여진 소스는 아래와 갈습니다.

void solve2()
{
    static unsigned primes[LIMIT/2];
    static uint64_t primesum[LIMIT/2];
    unsigned pcount = 0;

    primesum[0] = 0;
    primes[pcount++] = 2;
    primesum[pcount] = 2;
    primes[pcount++] = 3;
    primesum[pcount] = 5;

    for( unsigned p = 5 ; p < LIMIT ; p += 2 )
    {
        bool isPrime = true;
        for( int i = 1 ; primes[i]*primes[i] <= p ; i++ )
            if( p%primes[i] == 0 ) { isPrime = false; break; }
        if( isPrime )
        {
            primes[pcount++] = p;
            primesum[pcount] = primesum[pcount-1]+p;
        }
    }
    int max = 1, maxv = 2;
    for( int i = pcount-1 ; i > 0 ; i-- )
    {
        for( int j = 0 ; j < i-max ; j++ )
        {
            for( int k = j+max ; k < pcount ; k++ )
            {
                uint64_t sum = primesum[k] - primesum[j];
                if( sum > primes[i] ) break;
                if( sum == primes[i] )
                {
                    max = k-j;
                    maxv = primes[i];
                    break;
                }
            }
        }
    }
    printf("ans = %d(%d)\n", maxv, max);
}

실제 위 두개의 프로그램 중, solve1(...) 의 실행시간은 제 컴퓨터 환경에서 127.7초, solve2() 의 실행시간은 18.5초로 여전히 만족하지는 못하지만 처음 알고리즘에 비해서 비약적으로 발전했음을 알 수 있습니다.