This looks wrong:
bool number[n+1];
Try either std::vector<bool> number(n+1)
or bool* number = new bool[n+1]
Pergunta
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);
}
Solução 2
This looks wrong:
bool number[n+1];
Try either std::vector<bool> number(n+1)
or bool* number = new bool[n+1]
Outras dicas
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);
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.