Project Euler - 문제 10번

Summation of primes

Problem 10

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million.

 문제 10번 : 10보다 작은 소수의 합은 17이다. 그러면 200만 이하의 모든 소수의 합은 얼마인가?

---

 문제는 간단합니다. 그렇지만 소수 문제는 항상 시간을 얼마나 걸려서 답을 얻는지가 중요합니다. 이번 문제는 사실 앞서 문제 7번에서 썼던 코드를 살짝 고쳐서 사용하면 쉽게 답을 얻을 수 있습니다. 주의할 점은, 답이 int로 들어가지 않아섯 long long으로 정의하니 제대로 나오더군요.

#include <iostream>
#include "time.h"
#include "math.h"
using namespace std;

int main()
{
 clock_t start = clock();

 int j;
 long long result = 2;  // First prime number. 
 
 for(int i = 3; i < 2000000; i += 2)
 {
  for(j = 3; j*j < i; j += 2)
  {
   if(i%j == 0)
    break;
  }
  if(j > sqrt(i))
   result += i;
 }
    
 clock_t end = clock();
    cout << "Result : " << result << endl;
    cout << "Time : " << (long double)(end-start)/CLOCKS_PER_SEC;
    return 0;
}

 이 코드로 답을 얻는데 무려 0.365초나 걸렸습니다.

 제 코드는 아무리 줄여도 여기서 별반 차이가 나지 않을 것 같습니다. 그런데, 답을 입력하고 forum에서 보니까 소수의 합에 관한 아주 유용한 수학적인 툴이 있었습니다. 그 사람은 같은 구간동안 C++로 계산한 결과 700micro second가 걸렸다고 합니다. 즉, 0.0007초 인 셈인데, 제 코드보다 무려 500배나 빠른 셈이죠.

 자세한 수학적인 내용을 찾아서 올리려고 했는데 잘 안나오네요. 찾게 되면 업데이트 하겠습니다.