Sieve of eratosthenes

seive.c

#define N 1000001
int seive[N];
void fillSieve(){
    int i, j;
    seive[0] = seive[1] = 1; // 0, 1 aren't primes
    int n = sqrt(N);
    i = 2;
    for(j=2; i*j<N; j++)
        seive[i*j] = 1;
    for(i=3; i<=n; i+=2){
        if(seive[i])         // Anything marked 1 isn't prime
            continue;
        for(j=2; i*j<N; j++){
            seive[i*j] = 1;
        }
    }
}