Problem 10 : Summation of primes (5%)

link

Description

original

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

Find the sum of all the primes below two million.

간략해석

2백만보다 작은 소수의 합.

Idea & Algorithm

naive idea

에라토스테네스의 체의 시간복잡도는 $O(nloglogn)$이고, 충분히 구할 수 있다.

단, 범위가 int를 넘어가니 long long으로 하는 것이 중요하다.

advanced idea

source code

#include <stdio.h>
typedef long long ll;
const int MAX = 2000000

int arr[MAX];

int main(){
    ll tot = 0;
    for(ll i = 2; i < MAX; i++){
        if(arr[i]) continue;
        tot += i;
        for(ll j = i*i; j < MAX; j+=i){
            arr[j] = 1;
        }
    }
    printf("%lld",tot);
}

Problem 010