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

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

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

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

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

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

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

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

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

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

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

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

int main()
{
        int primes[11000];
        int count = 2;
        primes[0] = 2;
        primes[1] = 3;

        for( int i = 5 ; ; i+=2 )
        {
                int j;
                for( j = 1 ; primes[j]*primes[j] <= i ; j++ )
                        if( i%primes[j] == 0 ) break;
                if( i%primes[j] )
                {
                        primes[count++] = i;
                        if( count == 10001 ) break;
                }
        }
        printf("Ans = %d\n", primes[10000]);
}