Sly Guy

03-29-2013, 11:08 PM

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

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