10. Project Euler #10 : Sum of primes

Difficulty rating is 5%.

 

the Sieve of Eratosthenes

 

The task is to calculate all prime numbers below 2 million.
The solution is straightforward: use the Sieve of Eratosthenes to find primes below 2 million.
There are several algorithms to check if a number is prime, such as Miller-Rabin and AKS.

 

However, for this problem, I believe the Sieve of Eratosthenes is the best approach.

 

#include <stdio.h>
#include <stdint.h>

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

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

    for( int i = 5 ; i < 2000000 ; i+=2 )
    {
        int j;
        for( j = 1; primes[j]*primes[j] <= i ; j++ )
        {
            if( i%primes[j] == 0 ) break;
        }
        if( i%primes[j] )
        {
            primes[count++] = i;
            sum += i;
        }
    }
    printf("Ans = %jd\n", sum);
}