Why does my sieve get SIGSEGV

Question

Alright, so, just for fun, I was working on the sieve of eratosthenes. It was working fine intially so I sought out to improve its runtime complexity. and now, I on't know why, but I'm gettig a segmentation fault. Here's the code:

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    int* check = malloc(1000000000 * sizeof(int));
    long long int i;
    for(i = 0;i < 1000000000;i++)
    {
        check[i] = 0;
    }
    int j = 0;
    for(i = 2;i <= 1000000002;i++)
    {
         if(check[i] == 0)
         {
            printf("%lld\n", i);
            for(j = 1;j < (1000000001/i);j++)
            {
                check[j*i] == 1;
            }
         }
    }
return 0;   
}

Any help as to why it fails would be appreciated.

Answer 1

Your code has multiple errors, any of which could explain a segfault. First, you have not checked the return value of malloc, which may be NULL, even when you are totally sure it couldn't be.

Second, you are exceeding the bounds of the array you've allocated when you iterate i from 2 to 1000000002. With so many zeros it's hard to eyeball, so here are your figures with separators:

Initial allocation: 1,000,000,000
Range of i: 2 to 1,000,000,002 inclusive

At the end of that loop you are accessing memory past the end of your array.

Answer 2

#include <stdio.h>
#include <stdlib.h>

#if 1
static const size_t N = 1000 * 1000 * 1000;
#else
static const size_t N = 1000;
#endif

Don't use a magic number, define it as a constant. 1000000000 is also hard to read. Your C compiler can do calculation for you before it emits an executable. And you should have started with a small number. If you change #if 1 into #if 0, then the #else clause defining N as 1,000 will take effect.

int main(void)
{
    char* check = malloc(N + 3);

When you essentially use check as a boolean array, it doesn't have to be of type int. int occupies 4 bytes whereas char only 1 byte.

    if (NULL == check) {
        perror("malloc");
        abort();
    }

malloc silently returns NULL when it failed to find a memory chunk of the specified length. But if you work with 64 bit OS and compiler, I don't think it's likely to fail...

    long long int i;
    memset(check, 0, sizeof(check[0]) * (N + 3));

memset fills an array with the value of the 2nd parameter (here 0.) The third parameter takes the number of BYTES of the input array, so I used sizeof(check[0]) (this is not necessary for a char array becuase sizeof(char)==1 but I always stick to this practice.)

    int j = 0;
    for(i = 2;i <= N+2;i++)
    {
         if(check[i] == 0)
         {
            printf("%lld\n", i);
            for(j = 1;j < ((N+1)/i);j++)
            {
                check[j*i] = 1;

You wrote check[j*i] == 1 but it was an equality test whose result didn't have any effects.

            }
         }
    }
    free(check);

It is a good practice to always free the memory chunk that you allocated with malloc, regardless whether free is necessary or not (in this case no, because your program just exits at the end of sieve calculation.) Perhaps until you become really fluent with C.

return 0;   
}