CODEWITHSUNDEEP
cloopsruntime-errorsieve-of-eratosthenes
Mahmoud Elbrbry
Mahmoud Elbrbry

Reputation: 35

High limit in Sieve of Eratosthenes Algorithm for finding prime numbers makes the program stop working

I have used Sieve of Eratosthenes Algorithm to find the sum of prime numbers under certain limit and it has worked correctly until limit of 2 million, but when I tried 3 million the program has stopped while executing. 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;
}

Upvotes: 3

Views: 463

Answers (1)

Paul R
Paul R

Reputation: 213060

Most likely bool x[3000000]; will result in a stack overflow, as it will require more memory than is typically 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 wrong, since sum is declared as unsigned long long - change:

printf("%ld", sum);

to:

printf("%llu", sum);

If you're using a decent compiler (e.g. gcc) with warnings enabled (e.g. gcc -Wall ...) then the compiler should already have warned you about this error.

One further tip: don't use hard-coded constants like 3000000 - use a symbolic constant, and then you only have 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 instead.

Upvotes: 7

Related Questions