View Full Version : Implementation of Sieve of Eratosthenes Algorithm in C :]

Sly Guy
03-30-2013, 12:08 AM
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.

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;
*array = malloc((sizeof(int) * (*(count + 1))));
(*array) = sieve;
int i =0;
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.

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