Print first 1 million primes in 1 sec with constraints program size 50000 bytes and limited Memory

Question

I tried sieve of Eratosthenes: Following is my code:

void prime_eratos(int N) {
    int root = (int)sqrt((double)N);
    bool *A = new bool[N + 1];
    memset(A, 0, sizeof(bool) * (N + 1));
    for (int m = 2; m <= root; m++) {
        if (!A[m]) {
            printf("%d  ",m);
            for (int k = m * m; k <= N; k += m)
                A[k] = true;
        }
    }

    for (int m = root; m <= N; m++)
        if (!A[m])
            printf("%d  ",m);
    delete [] A; 
}

int main(){

    prime_eratos(179426549);
    return 0;
}

It took time : real 7.340s in my system.

I also tried Sieve of Atkins(studied somewhere faster than sieve of Eratosthenes).

But in my case,it took time : real 10.433s .

Here is the code:

int main(){
    int limit=179426549;
    int x,y,i,n,k,m;
    bool *is_prime = new bool[179426550];

    memset(is_prime, 0, sizeof(bool) * 179426550);

    /*for(i=5;i<=limit;i++){
      is_prime[i]=false;
      }*/
    int N=sqrt(limit);
    for(x=1;x<=N;x++){
        for(y=1;y<=N;y++){
            n=(4*x*x) + (y*y);
            if((n<=limit) &&(n%12 == 1 || n%12==5))
                is_prime[n]^=true;
            n=(3*x*x) + (y*y);
            if((n<=limit) && (n%12 == 7))
                is_prime[n]^=true;
            n=(3*x*x) - (y*y);
            if((x>y) && (n<=limit) && (n%12 == 11))
                is_prime[n]^=true;
        }
    }
    for(n=5;n<=N;n++){
        if(is_prime[n]){
            m=n*n;
            for(k=m;k<=limit;k+=m)
                is_prime[k]=false;

        }
    }
    printf("2   3   ");
    for(n=5;n<=limit;n++){
        if(is_prime[n])
            printf("%d   ",n);
    }
    delete []is_prime;
    return 0;
}

Now,I wonder,none is able to output 1 million primes in 1 sec.

One approach could be:

     I store the values in Array but the program size is limited.

Could someone suggest me some way to get first 1 million primes in less

than a sec satisfying the constraints(discussed above) ?

Thanx !!

Answer 1

You've counted the primes incorrectly. The millionth prime is 15485863, which is a lot smaller than you suggest.

You can speed your program and save space by eliminating even numbers from your sieve.

Answer 2

Try

int main()
{
    std::ifstream  primes("Filecontaining1MillionPrimes.txt");
    std::cout << primes.rdbuf();
}

Answer 3

The fastest way I know to check if a number is prime is to check for compositeness, I've implemented the http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test with great sucess for RSA, it is probabilistic, with high degree of success depending on how many times you run it.

Answer 4

Step 1. don't do a printf

Step 2. buy a faster computer.