View Single Post
 03-30-2013, 12:08 AM PM User | #1 Sly Guy New to the CF scene   Join Date: Mar 2013 Posts: 1 Thanks: 0 Thanked 0 Times in 0 Posts 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