Compute Primes

primes.cpp

/* Calculate primes upto the first 10^6 numbers
 * Checked and tested the first 1000 primes for sanity sake
 */
#define PRIME_SIZE 500000 // Half of 10^6, we really don't need to store even numbers
#define PRIME_SIZE_ROOT 708 // precomputed sqrt(PRIME_SIZE)
#include<iostream>
#include<cstdio>


using namespace std;

int main() {
    // Precompute a sieve of numbers
    int P[PRIME_SIZE];
    memset(P, 0, sizeof(P)); // Set array to 0s

    int i=0;
    for(i=3; i<PRIME_SIZE_ROOT; i+=2) {
        for(int j=3*i; j<PRIME_SIZE; j+=2*i) {
            P[(j-3)/2]=1;
        }
    }

    for(int k=0; k<PRIME_SIZE; k++) {
        if(P[k]==0) printf("%d\n", k*2 + 3);
    }


    return 0;
}