High limit in the sieve of Eratosthenes The prime number search algorithm causes the program to stop working
I used the Sieve of Eratosthenes algorithm to find the sum of the primes at a certain limit, and it worked correctly up to the 2 million limit, but when I tried 3 million, the program stopped during execution. Here is the code:
int main(){
bool x[3000000];
unsigned long long sum = 0;
for(unsigned long long i=0; i< 3000000; i++)
x[i] = true;
x[0] = x[1] = false;
for(unsigned long long i = 2; i < 3000000; i++){
if(x[i]){
for (unsigned long long j = 2; i * j < 3000000; j++) {
x[j*i] = false;
}
sum += i;
}
}
printf("%ld", sum);
return 0;
}
source to share
Most likely bool x[3000000];
will result in a stack overflow since it will require more memory than is normally available on the stack. As a quick fix, change this to:
static bool x[3000000];
or consider using dynamic memory allocation:
bool *x = malloc(3000000 * sizeof(*x));
// do your stuff
free(x);
Also note that your printf format specifier is incorrect as it is
sum
declared as
unsigned long long
- change:
printf("%ld", sum);
in
printf("%llu", sum);
If you are using a decent compiler (like gcc) with warnings enabled (like gcc -Wall ...
), the compiler should have warned you about this error already.
One more tip: don't use hardcoded constants like
3000000
- use a symbolic constant and then you only need to define the value in one place - this is known as the "Single Point Of Truth" (SPOT) principle, or "Don't repeat yourself" (DRY ):
const size_t n = 3000000;
and then wherever you are currently using 3000000
, use n
.
source to share