Sieve of Eratosthenes algorithm in C

c, dangling-pointer, primes, sieve, sieve-of-eratosthenes

Solution

void getPrimes(int num, int* count, int** array){
    (*count) = (num - 1);
    int sieve[num-1], primenums = 0, index, fillnum, multiple;

You're declaring an array of `num-1` elements, for the numbers from 2 through `num`. That's okay.

    //Fills the array with the numbers up to the user's ending number, num.
    for(index = 0, fillnum = 2; fillnum <= num; index++, fillnum++){
        sieve[index] = fillnum;
    }

You're filling each slot with the number it associated with, also okay.

     /* Starts crossing out non prime numbers starting with 2 because 1 is not a prime.
        It then deletes all of those multiples and 
        moves on to the next number that isnt crossed out, which is a prime. */
     for (; primenums < sqrt(num); primenums++) //Walks through the array.

You're stopping roughly at the square root, that's good.

        {
            if (sieve[primenums] != 0){ //Checks if that number is NULL which means it's crossed out

                   for (multiple = (sieve[primenums]); multiple < num; multiple += sieve[primenums])
                      //If it is not crossed out it starts deleting its multiples.
                   {  //Crossing multiples out and decrements count to move to next number
                            sieve[multiple + primenums] = 0;

You're having a problem here. You only stop the loop when `multiple >= num`, but you're writing to the index `multiple + primenums`, and that is often past the end of the array. For example, with `num == 19`, and `primenums == 1` (which crosses out the multiples of 3), the last write is to index `18 + 1`, but the last valid index is `num - 2 = 17`.

The indexing bias of point 1 has been fixed. But

                            --(*count);

You're unconditionally decrementing `*count` here, in the earlier code you only decremented it when `sieve[multiple]` was not already crossed out. That is the correct way. I suggest

for(multiple = primenums + sieve[primenums]; multiple < num - 1; multiple += sieve[primenums]) {
    if (sieve[multiple]) {
         sieve[multiple] = 0;
         --(*count);
    }
}

to have it a bit simpler.

                   }
            }
        }
        int k;
        for(k=0; k < num; k++)
            printf("%d \n", sieve[k]);

You're printing the contents of `sieve` regardless of whether it is `0` or not, and you also print out `sieve[num - 1]`, which does not exist. Make it

for(k = 0; k < num-1; ++k) {
    if (sieve[k]) {
        printf("%d\n", sieve[k]);
    }
}

to print only the primes.

            printf("%d \n", *count);
        array = malloc(sizeof(int) * (num + 1));
         assert(array);
         (*array) = sieve;
}

Replace the `(*array) = sieve` with

int i = 0;
for(k = 0; k < num-1; ++k) {
    if (sieve[k]) {
        (*array)[i] = sieve[k];
        ++i;
    }
}

to write only the primes to `*array`. Also, you need not allocate `(num + 1)*sizeof(int)`, but only `*count * sizeof(int)` for that.

Problem

Original source