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);
}

score 3 · Answer 1 · answered Jan 19 '14 at 21:26

3

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);

answered Jan 19 '14 at 21:26

Ben Voigt

277,958
43
419
720

What do you mean by `even in g++`. What is that implying about g++? – BWG Jan 19 '14 at 21:33
@BWG There is no implying here, a g++ expansion makes it possible but even with this extension its not a good thing to do o.O – Sebastian Hoffmann Jan 19 '14 at 21:40
@BWG: I mean that other compilers will reject that outright. g++ will try to make it work but failure then occur silently at runtime, so even if you have g++ (which accepts these C99-style VLAs) you should not use them. – Ben Voigt Jan 19 '14 at 21:40
If anything, what I'm implying is that **g++ support for VLAs is a bug not a feature**. There, I said it clearly. – Ben Voigt Jan 19 '14 at 21:40
and what do you mean by "vector is a weird beast" please? I thought `vector` was automatically bit-packed (taking 8x less space than `vector` of same length). – Will Ness Jan 19 '14 at 22:15
@Will: Yes, it is, via template specialization. And it also does not meet the container requirements. – Ben Voigt Jan 19 '14 at 22:16
@WillNess: See http://stackoverflow.com/questions/670308/alternative-to-vectorbool and http://stackoverflow.com/q/15617501/103167 and http://isocpp.org/blog/2012/11/on-vectorbool – Ben Voigt Jan 19 '14 at 22:22
OK, for the benefit of other readers, the refs say *"`vector` is not a container as its reference and pointer types are not references and pointers."* – Will Ness Jan 19 '14 at 22:26
And because access to different elements can still be a conflict (in the threading sense) – Ben Voigt Jan 19 '14 at 22:28

score 1 · Accepted Answer · answered Jan 19 '14 at 21:26

1

This looks wrong:

bool number[n+1];

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

answered Jan 19 '14 at 21:26

Sorin

11,863
22
26

Had to wait 8 minutes :P – user2421892 Jan 19 '14 at 21:46
1

Note that the "working" line also causes a memory leak. Probably not problematic in this use case, where `main()` immediately exits taking the memory with it. But good to be aware of. – Ben Voigt Jan 19 '14 at 22:18

score 1 · Answer 3 · answered Jan 19 '14 at 21:28

1

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.

answered Jan 19 '14 at 21:28

tumdum

1,981
14
19

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

3 Answers3