# Implementation of Sieve of Eratosthenes Algorithm in C :]

• 03-29-2013, 11:08 PM
Sly Guy
Implementation of Sieve of Eratosthenes Algorithm in C :]
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.

Code:

```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. */         int j = 0;         for (; primeNums < (usernum - 1); ++primeNums, j++)        //Walks through the array.         {                         if (sieve[j]){          //Checks if that number is NULL which means it's crossed out                                           for (multiple = (sieve[j])*2; multiple < usernum; multiple = multiple + (sieve[j]))                   //If it is not crossed out it starts deleting its multiples.                   {                         if (sieve[multiple]) {            //Crossing multiples out and decrements count to move to next number                                                         *(sieve + multiple) = 0;                             --(*count);                           }                   }             }         }         *array = malloc((sizeof(int) * (*(count + 1))));                 assert(*array);         (*array) = sieve;         int i =0;         for(;i<usernum;i++){                         if(sieve[i] != NULL)                         printf("%d ", sieve[i]);                 } }```
Now, here is the intended output and my output. As you can see, something is wrong within my getPrimes function but I am unsure as to what.

PHP Code:

``` Intended Output: There are 8 prime numbers less than or equal to 19 2 3 5 7 11 13 17 19 My Output: 2 3 4 5 7 9 13 15 19  ```
Can anyone spot where I went wrong? I'm dying to figure out what I am missing it feels like I'm so close, this is a HW question, but I wrote all this code the instructions were basically what was at the top and I had to start completely fresh.

I'd truly appreciate any help that can be giving.

Thank you in advance,
Sly Guy