Segmentation Fault with Sieves of Eratosthenes algorithm in C

Question

Okay, so this function I created uses the Sieve of Eratosthenes algorithm to compute all the primes <= n. This function stores the prime numbers and the count of primes in the parameters.

When the function exits, primes should be pointing to a chunk of dynamically allocated memory that holds all the primes <= num. *count will have the count of primes.

Here is my function getPrimes:

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

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

     /*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(usernum); primenums++){ //Walks through the array.
         if (sieve[primenums] != 0){ //Check's if that number is 0 which means it's crossed out
             for (multiple = (sieve[primenums]); multiple < usernum; 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;
                 --(*count);
             }
         }
     }
     int k;
     for (k = 0; k < usernum; k++)
     if (sieve[k] != 0){
         printf(" %d", sieve[k]);
     }
     printf(" ");
     array = malloc(sizeof(int) * (usernum + 1));
     assert(array);
     (*array) = sieve;
 }

My function here compiles perfectly, however I noticed I have a segmentation fault when I try larger numbers from like 101 on. Does anyone see where my code is producing a segmentation fault?

If you run your code in the debugger, it will tell you where the seg-fault is. What's more, you'll be able to inspect the values of variables, etc. — Oliver Charlesworth, Mar 30 '13 at 01:29
You are in the perfect position to do this yourself. Like I said, run this in a debugger. — Oliver Charlesworth, Mar 30 '13 at 01:31
Well, I don't know what platform you're on. If you're using an IDE (e.g. Visual Studio or Eclipse), then there should be a built-in debugger you can use. If you're running at the Linux command-line, then use GDB. — Oliver Charlesworth, Mar 30 '13 at 01:33
EXACT SAME question asked by same user here: http://stackoverflow.com/questions/15712513/sieve-of-eratosthenes-algorithm-in-c — joce, Mar 30 '13 at 01:34
"EXACT SAME"?! Are you kidding. This involves a segmentation fault with my running code now. It isn't a duplicate. — Hetero Myde, Mar 30 '13 at 01:35
Also, Oli...I tried using GDB with no luck. Not sure why it didn't work. So I would definitely appreciate some help from the people on SO. — Hetero Myde, Mar 30 '13 at 01:39
Ok, to be honest, it sounds like you'd prefer someone else solved your problem for you, rather than spending any time learning how to do your own debugging. That's not a good approach. If not, then prove me wrong by editing your question to describe what you found with GDB... — Oliver Charlesworth, Mar 30 '13 at 01:54
You're right. I've been working on this for a long time and just want it to be over with...not a very good approach indeed lol. — Hetero Myde, Mar 30 '13 at 01:54

score 1 · Answer 1 · edited May 23 '17 at 11:57

The following two statements are problems:

array = malloc(sizeof(int) * (usernum + 1));

I think you meant to do *array = malloc..., note the asterisk I added before array. You want to dereference the int** parameter in order modify the caller's pointer.

(*array) = sieve;

This code doesn't copy the array, it assigns the address of a temporary local variable to the caller's pointer. The sieve array will no longer exist after it goes out of scope at the end of the function. You want to use a for loop to copy the contents from sieve to the memory block you just allocated.

Edit:

I see that Daniel Fischer already pointed out the second problem 3 hours ago in a previous incarnation of your question.

Segmentation Fault with Sieves of Eratosthenes algorithm in C

1 Answers1