7. 프로젝트 오일러 #7 : 10,001번째 소수 찾기

큰 수에 대한 소수를 찾는 것이라면, 응당 다른 방법을 택해야 하겠지만,

비교적 작은 소수에 대해서는 에라스토테네스의 체 이상 가는 알고리즘이 별로 없습니다.

 

Sieve of Eratosthenes

 

특히 이번 문제와 같이 10,0001번째 소수 찾기라면 더더욱 말이죠.

 

알고리즘 자체는 아주 간단합니다.

소수를 저장할 수 있는 배열 공간을 잡고, 여기에 차곡차곡 소수를 담아넣습니다.

일단 2를 제외한 모든 소수는 홀수이므로, 검사해야 하는 수를 절반으로 줄일 수 있습니다.

 

2를 제외한다면, 소수는 다음과 같이 표현될 수 있습니다.

\[ 2k + 1 \]

 

2와 3을 제외한다면, 소수는 다음과 같이 표현될 수 있습니다.

\[ 6k \pm 1 \]

 

2, 3, 5를 제외한다면, 소수는 다음과 같이 표현됩니다.

\[ 30k + r ~where~ (30, r) = 1 \]

 

일반적으로 우리는 오일러 수만큼 해당하는 소수만 검사하면 됩니다. 제외하는 소수가 몇개이든 상관없이요. 그렇게 해서 우리가 조사해야할 범위를 줄일 수 있지만, 그것으로 엄청나게 좋은 결과를 얻을 수는 없습니다. 2를 제외할 경우에는 50%, 2, 3을 제외할 경우에는 33.3%, 2, 3, 5를 제외할 경우에는 26.6% 식으로 줄어들긴 하겠지만, 그럴수록 프로그램 복잡도는 늘어나게 되겠죠.

 

그래서 여기서는 2라는 소수만 제외하도록 했습니다. 그대신, 이제까지 구해진 모든 소수를 다 검사하는 것이 아니고, 소수의 제곱이 현재수보다 작거나 같은 경우만 검사하도록 함으로써, 다른 알고리즘과의 차별성을 두었습니다.

//----------------------------------------------------------
//    Project Euler #007
//        - by Aubrey Choi
//----------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <time.h>
#include <math.h>
#include "isprime.h"

#define    N    10001

void solve1()
{
    int primes[N];
    int count = 0;

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

    for( int p = 5 ; count < N ; 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[count++] = p;
    }
    printf("Ans = %d\n", primes[N-1]);
}

int main()
{
    clock_t t;

    t = clock();
    solve1();
    printf("Elapsed time is %.3f seconds \n", (float)(clock() - t) / CLOCKS_PER_SEC);

    return 0;
}