value requires 1000000000 bytes, which is more than max-value-size

Question

I am stuck with this problem on spoj.com

http://www.spoj.com/problems/PRIME1/

After reading a bit about prime generation algorithms, I found that "Sieve of Atkins" is the fastest prime generation algorithm. I have partially implemented the algorithm with the help of this tutorial http://www.geeksforgeeks.org/sieve-of-atkin/

When I ran the code, it gave me segmentation fault. After debugging I came to know that this code is not optimal, it uses more memory, storage. Could someone tell me how can I optimise the program. Here is my code snippet. And yeah, it is incomplete.

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int sieveOfAtkin(long int limit)
{
    // if limit is either 2 or 3, print them
    if (limit >= 2)
    {
        cout << 2 << endl;
    }

    if (limit >= 3)
    {
        cout << 3 << endl;
    }


    bool sieve[limit];
    for (long int i=0; i<=limit; i++)
        sieve[i] = false;

    for (long int x=1; x<limit; x++)
    {
        for (long int y=1; y<limit; y++)
        {

            long int n = (4*x*x) + (y*y);
            if (n<=limit && (n%12==1 || n%12==5))
                sieve[n] ^= true;

            n = (3*x*x) + (y*y);
            if (n<=limit && (n%12==7))
                sieve[n] ^= true;

            n = (3*x*x) - (y*y);
            if (x>y && n<=limit && (n%12==11))
                sieve[n] ^= true;
        }
    }

    for (long int r=5; r*r<limit; r++)
    {
        if(sieve[r])
        {
            for(long int i=r*r; i<limit; i+=r*r)
                sieve[r] = false;
        }
    }

    for (long int i=5; i<limit; i++)
        if(sieve[i])
            cout << i << endl; 

    return 0;
}

int main(void)
{
    long int x;
    cin >> x;
    sieveOfAtkin(x);
    return 0;
}

---

Answer 1

First, it is an internet myth that the Sieve of Atkin is faster than the Sieve of Eratosthenes. The Sieve of Atkin is faster under certain constraints, but the Sieve of Eratosthenes is faster in general and is the sieve chosen by mathematicians who actually use it to investigate prime numbers.

Second, when the sieve gets too large to fit in memory you can segment the sieve. See this answer for details.