C++ Sieve of Eratosthenes algorithm results in stack overflow

Question

I was working on a simple Sieve of Eratosthenes algorithm and the code is below:

int main()
{

    const int n = 1000000;

    int sqrn = floor(sqrt(n));

    bool primes[n + 1] = { 0 }; // false means prime, true not prime

    primes[0] = true;
    primes[1] = true;

    for (int i = 2; i <= sqrn; i++){

        if (primes[i] == false) {
            int j = i + i;
            while (j<=n-1){
                primes[j] = true;
                j = j + i;
            }
        }
    }
}

My main question is that this code results in stack overflow error if I try to set the search array to greater than n=1000000. I am not sure if this is because a programming error or because of the program can not hold a boolean array larger than 10^6 entries? Any advice is appreciated.

Another minor question I have is whether setting the evaluation of the square root of n outside the for-loop statement improves execution speed.

Thank you

Answer 1

Instead of bool primes[n + 1] = { 0 };, do:

std::vector<bool> primes(n+1);

This allocates non-stack space for enough primes, and initializes them all to false.

This version has another advantage in that the compiler may specialize it to use one bit per value, whereas your version used one byte per value.

A similar alternative that may have better performance (but is only possible when the size is known at compile-time) is

std::bitset<n+1> primes;

If you look up its documentation you may be able to improve your code's performance.

Answer 2

You are allocating the primes array on the stack. The stack only has a limited size (it's pretty big, but it's still limited). You can either:

• allocate your array in the global data area, or
• allocate your array on the heap with new

Answer 3

The stack overflow is likely because your stack is not just under 1MB (or 1MB depending on your definition) in size. bool is usually 1 byte. Try allocating the primes array on the heap (using new[]) to avoid the stack size limitation. Remember to release the array with delete[].

Also the primality of n will be incorrect from this algorithm. You want to change j<=n-1 to j<=n.