Project Euler #10 - C

Question:

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

Find the sum of all the primes below two million.

Solution:

Again we have a problem where we are asked to deal with prime numbers, and again I will employ the Sieve of Eratosthenes to solve this problem. Basically, find a prime, delete its multiples (set to 0 in the array), and then find the next non-zero entry in the array. As we find these primes, we accumulate their total. 

The only problem while programming this in C is that the array will have to be quite large and (at least on my system) has to be declared as static as to not overflow the stack. Other than that, I believe the code is simple and straightforward. 

#include <stdio.h>
#define LIMIT 2000000


static int numArray[LIMIT] ={0}; // zero out array


int main (void)
{
int i;
long long result = 2;
int last_prime = 2; 
int prime_found = 1;


for (i = 1; i < LIMIT; i+=2) // leave out even numbers
numArray[i] =  i; // Populate array 


/* Find the next prime, then delete all multiples of it (set to 0) */


while (prime_found) // Go until there are no more primes
{
int j;
prime_found = 0;


for (i = last_prime+1; i < LIMIT; i++)
{
if (numArray[i] != 0) // If not 0, then it is prime. 
{
last_prime = i; 
result += i;
prime_found = 1;
break;
}
}


if (prime_found) // Found prime, delete its multiples
{
for ( j = 2; j < LIMIT; j++ )
{
if ( j*last_prime > LIMIT )
break;


numArray[j*last_prime] = 0;
}
}
}


printf("The sum of all primes below %d is %lld \n\n", LIMIT, result);

return 1;
}