Program stops working when making big table (2'000'000+)

Question

I wrote this program using Sieve of Eratosthenes. It is supposed to output prime numbers up to 2'500'000, but it crashes when trying to create array bigger than ~2'100'000. Any ideas what might be broken?

Compiling with gcc in Code::Blocks (Windows 8.1, shame on me).

PS It works flawless for N <= 2'000'000

#include <stdio.h>

int main() {
    // Input
    long n;
    scanf("%ld", &n);

    // Initialize vars
    bool number[n+1];
    for(long i = 0; i < n; i++)
        number[i] = false;

    // Main loop
    for(long i = 2; i*i <= n; i++) {
        if(number[i]) // If number is already removed
            continue; // Do next number

        // Remove x * i
        for(long j = i*2; j <= n; j += i)
            number[j] = true;
    }

    // Print
    for(long i = 2; i <= n; i++)
        if(!number[i]) printf("%ld ", i);
}

Answer 1

This looks wrong:

bool number[n+1];

Try either std::vector<bool> number(n+1) or bool* number = new bool[n+1]

Answer 2

This is not valid C++, if n is not a constant integral expression (yours isn't):

bool number[n+1];

It is a g++ extension, and puts the array on the call stack, which has limited size. You're overflowing it, causing an immediate program crash (no exception to recover from) so this is a bad idea even in g++.

Try

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

(Note you'll need #include <vector> to make that work)

Also note that vector<bool> is a weird beast. Should work just fine for your usage, but to get something closer to bool[], you can also try

std::vector<char> number(n+1);

Answer 3

You are trying to allocate array of n bools on stack, which might be simply to small. Try allocating on heap with std::vector or new operator.