Sieve of Eratosthenes C implementation error

Question

So I am making next homework with input numbers to be dissolved to primes multiplication in output. I was confused when it showed up only prime number 2, so I did a proper control dump of the allocated primes array using this function:

long* eratosthen(long max) {
    bool grid[max + 1];

    for(long i = 0; i < max + 1; ++i) {
        grid[i] = true;
    }

    for(long i = 2; i < max + 1; ++i) {
        if(grid[i]) {
            for(long j = i * 2; j < max + 1; ++j) {
                grid[j] = false;
            }
        }
    }

    long *primes;
    primes = (long*)malloc((max + 1) * sizeof(long));

    long index = 0;
    for(long i = 2; i < max + 1; ++i) {
        if(grid[i]) {
            primes[index++] = i;
        }
    }

    return primes;
}

For some unknown reason, the dump says 2 only and ends. Calling for dump is made up by following code:

int main(void) {
    // Prime numbers get calculated first
    long *primes;
    primes = eratosthen(1000000);

    // Control code
    fprintf(stdout, "Control dump of primes array:\n");
    for(long i = 0; i < sizeof(primes) / sizeof(long); ++i) {
        fprintf(stdout, "%li\n", primes[i]);
    }
    int ret = 0;
    /// ...
    return ret;
}

//EDIT: So after all your answers I'll update my question to current state. Main program: int main(void) { // Prime numbers get calculated first long *primes; primes = eratosthen(1000000);

    // Control code
    fprintf(stdout, "Control dump of primes array:\n");
    for( ; *primes != 0 ; primes++) {
        fprintf(stdout, "%li\n", *primes);
    }
    int ret = 0;
}

Generation of primes function:

long* eratosthen(long max) {
    bool *grid;
    grid = (bool*)malloc((max + 1) * sizeof(bool));

    index = 0;
    for(long i = 0; i < max + 1; ++i) {
        *(grid + index) = true;
        index++;
    }

    index = 2;
    index_2 = 2;
    for(long i = 2; i < max + 1; ++i) {
        if(*(grid + index)) {
            for(long j = i * 2; j < max + 1; j += i) {
                *(grid + 2 * index_2) = false;
                index_2++;
            }
            index++;
        }
    }

    long *primes;
    primes = (long *)malloc((max + 1) * sizeof(long));

    index = 0;
    for(long i = 0; i < max + 1; ++i) {
        *(primes + index) = 0;
        index++;
    }

    index = 0;
    index_2 = 2;
    for(long i = 2; i < max + 1; ++i) {
        if(*(grid + index_2)) {
            *(primes + index) = i;
            index++;
            index_2++;
        }
    }

    // free the grid
    free(grid);

    return primes;
}

Like said before, the Ubuntu terminal displays following line:

Neoprávněný přístup do paměti (SIGSEGV) (core dumped [obraz paměti uložen])

translated like this:

Forbidden access to memory (SIGSEGV) (core dumped [memory image saved])

What does it mean and how to get rid of that? :(

Answer 1

The simplest fix to your code is probably to add a sentinel value of 0 to the end of the array of primes, and to rewrite the check condition in main(). As explained extensively in the comments, your current test:

for(long i = 0; i < sizeof(primes) / sizeof(long); ++i) {

is irremediably wrong. You must not attempt to use sizeof because it simply doesn't do what you want it to do.

This code works:

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

static
long *eratosthen(long max)
{
    bool grid[max + 1];

    for (long i = 0; i < max + 1; ++i)
        grid[i] = true;

    for (long i = 2; i < max + 1; ++i)
    {
        if (grid[i])
        {
            for (long j = i * 2; j < max + 1; j += i)   // Key fix
                grid[j] = false;
        }
    }

    long *primes;
    primes = (long *)malloc((max + 1) * sizeof(long));

    long index = 0;
    for (long i = 2; i < max + 1; ++i)
    {
        if (grid[i])
            primes[index++] = i;
    }
    primes[index] = 0; // Sentinel

    return primes;
}

int main(void)
{
    // Prime numbers get calculated first
    long *primes = eratosthen(1000000);

    fprintf(stdout, "Control dump of primes array:\n");
    for (long i = 0; primes[i] != 0; ++i)
    {
        printf("%7li", primes[i]);
        if (i % 10 == 9)
            putchar('\n');
    }
    putchar('\n');
    return 0;
}

I revised the code to print 10 numbers per line. I changed the condition in the loop in main(). And I made two key changes in the function — one to calculate multiples of primes correctly, and the other to add the sentinel at the end of the list of primes.

It produces a list of 78,498 primes starting with

      2      3      5      7     11     13     17     19     23     29
     31     37     41     43     47     53     59     61     67     71
     73     79     83     89     97    101    103    107    109    113

and ending with:

 999563 999599 999611 999613 999623 999631 999653 999667 999671 999683
 999721 999727 999749 999763 999769 999773 999809 999853 999863 999883
 999907 999917 999931 999953 999959 999961 999979 999983

You might note that the code does not release primes — it arguably should. You might note that the space allocated for the primes greatly exceeds the space needed (one million vs less than eighty thousand); you could use realloc() to shrink the space allocated, or use a less conservative (or do I mean less profligate?) estimate on the number of entries needed.