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++){
            for (unsigned long long j = 2; i * j < 3000000; j++) {
                x[j*i] = false;
            sum += i;

    printf("%ld", sum);

    return 0;



source to share

1 answer

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



Also note that your printf format specifier is incorrect as it is sum

declared asunsigned long long

- change:
printf("%ld", sum);



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




All Articles