[Project Euler #10][C++]이백만 이하 소수의 합

문제10 : 이백만 이하 소수의 합

문제

10 이하의 소수를 모두 더하면 2 + 3 + 5 + 7 = 17 이 됩니다.

이백만(2,000,000) 이하 소수의 합은 얼마입니까?

문제 해결 방법

하나하나씩 계산하는 방식(브루트 포스 방식)으로 문제를 해결하였다. (에라토스네스 체 알고리즘 사용)

• 정답을 구하는데 약 20분 이 걸렸다. (...)
• for 문을 사용하여 문제를 해결하였다.
  • 2부터 N(2000000)까지 순회를 하며 소수를 찾으면 sum 변수에 대입하고 더하는 과정을 반복하였다.
• 최종적으로 sum 변수에 할당된 값을 출력하도록 하였다.

소스 코드

#include <iostream>
using namespace std;
 
#define N 2000000
 
bool isPrimeNum(int n);
 
int main() {
    unsigned long long int sum = 0;
 
    for (register int i = 2; i <= N; i++) {                                                                                     
        if (isPrimeNum(i) == true) {
            sum += i;
        }
    }
 
    cout << sum << endl;
 
    return 0;
}
 
bool isPrimeNum(int n) {
    for (int i = 2; i < n; i++) {
        if ((n % i == 0) && (n != i)) {
            return false;
        }
    }
    return true;
}

정답

142913828922

심화 공부

소수의 합(Prime Sums)

처음 $n$개 소수의 합은, $n$이 작은 경우 에라토스테네스의 체 등으로 직접 구하는 것이 빠르고, $n$이 매우 클 경우 는 어림할 수 밖에 없다. 처음 몇 소수의 합은 2, 5, 10, 17, 28, 41, 58, 77, ... 이다. 에라토스테네스의 체를 구성할 수 없을 정도로 $n$이 매우 큰 경우 소수의 합은 다음과 같이 어림할 수 있다. 이백만 이하 소수의 합에 대해 아래 공식을 적용하면 대략 7.6%의 오차가 발생한다.

$$ \sum _{k=1}^{n}{p_k} ∼ \frac {1} {2} n^2 \ln{n} $$

참고로, 1737년에 오일러는 소수 역수의 합이 매우 느리지만 결국에는 무한대로 발산한다는 것을 보였다.

$$ \sum _{k=1}^{\infty}{\frac {1} {p_k}} = \infty$$

---

문제 출처 : https://euler.synap.co.kr/problem=10