Project Euler #7 - C

Question:

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10001st prime number?

Solution:

This problem can be solved using a Sieve of Eratosthenes. But, we must make sure that our array is large enough to find the desired prime. In this case, I figured half a million should suffice (and it does). To "cross out" an item in our array, we simply set it to 0. We then employ the sieve method until we discover our desired prime. In other words, go to the next number that isn't 0 and delete all multiples of that number in the array. Rinse and repeat.

#include <stdio.h>
#define MAX 500000
#define target_prime 10001


int main (void)
{
unsigned int primes[MAX];
int last_found = 1; 
int primes_found = 1;
int i;


for (i = 0; i < MAX; i++) // populate array
primes[i] = i;


/* Find and eliminate all non-primes beginning with the last                 found prime + 1*/


while (primes_found <= target_prime)
{
for (i = 1; i <= MAX; i++)
{
if( primes[last_found+i] != 0 ) // This number    is not zero, so it is prime
{
last_found = last_found+i;  
break;
}
}

/* eliminate all multiples of this prime */
int j = 2;


for( j = 2; j < MAX; j++)
{
if (last_found * j > MAX)
break;
primes[last_found * j] = 0;
}


primes_found++;
}


printf("Prime #%d is %d\n", target_prime, last_found);


return 1;
}


I don't think this code requires any extra commentary. Compile and watch the answer appear before your eyes!