10. 프로젝트 오일러 #10 : 2백만 이하의 소수의 합 구하기

사실 이번 문제는 에라스토테네스의 체를 이용하는 것 이외에는 별다른 좋은 방법은 없어보입니다.

큰 수에 대해서는 효율적인 알고리즘을 개발할 수 있지만, 2백만이라는 비교적 작은 수에 대한 것이라서 간단하게 짜보았습니다.

#define LIMIT   2000000

void solve1()
{
    int primes[200000];
    int count = 0;
    int64_t sum = 0;

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

    for( int 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[count++] = p; sum += p;
        }
    }
    printf("Ans = %jd\n", sum);
}