소수의 합 [C++]

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

#include <vector> #include <cmath> using namespace std; long long solution(int N) { long long answer = 0; bool *numbers = new bool[N+1]; for(int i=2; i<=N; i++) numbers[i] = true; for(int i=2; (i*i)<=N; i++) { if(!numbers[i]) continue; if(numbers[i]) { for(int j=(i*i); j<=N; j+=i) { numbers[j] = false; } } } for(int i=2; i<=N; i++) { if(numbers[i]) { answer += i; } } return answer; }

- 코드 설명

에라토스테네스의 체를 이용하여 소수를 구한 뒤, 2부터 N까지의 모든 소수를 answer에 더해준다.