Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why do I fail Project Euler #10?

Question is: Find the sum of all the primes below 2 million.

I pretty much did the Sieve of Erastothenes thing, and the program below seems to work for small number i.e. define LIMIT as 10L produces 17 as answer.

I submitted 1179908154 as the answer, as produced by the following program, and it was incorrect.

Please help pointing out the problem. Thanks.

#include <stdio.h>

#define LIMIT 2000000L
int i[LIMIT];

int main()
{
    unsigned long int n = 0, k, sum = 0L;
    for(n = 0; n < LIMIT; n++)
        i[n] = 1;
    i[0] = 0;
    i[1] = 0;

    unsigned long int p = 2L;

    while (p*p < LIMIT)
    {
        k = 2L;
        while (p*k < LIMIT)
        {
            i[p*k] = 0;
            k++;
        }
        p++;
    }

    for(n = 0; n < LIMIT; n++)
        if (i[n] == 1)
        {
            sum += n;
        }
    printf("%lu\n",sum);

    return 0;
}
like image 938
idazuwaika Avatar asked Jan 01 '10 14:01

idazuwaika


1 Answers

You calculate the primes correctly, but the sum is too large (over 2^32) and won't fit in an unsigned 32-bit long. You can use a 64-bit number (long long on some compilers) to fix this.

like image 122
interjay Avatar answered Sep 28 '22 09:09

interjay