...

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;
--(*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.


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



EZ Archive Ads Plugin for vBulletin Copyright 2006 Computer Help Forum