Contents

#include <string.h>
#include <stdlib.h>
#include <math.h>
#include "sieve.h"

unsigned int sieve(const unsigned int limit, primesArray_t primes)
{
   unsigned int numberOfPrimes = 0;
   unsigned char *numberIsPrime;

   // clear the results
   memset(primes, 0, sizeof(*primes));

   if (limit > 1) {
      //allocate 1 more than limit for convenience so the number and the index are same
      numberIsPrime = malloc(limit + 1);
      memset(numberIsPrime, 1, limit + 1);

      unsigned int maxFactor = sqrt(limit) + 1;

      // mark 0 and 1 as not prime
      for (unsigned int i = 0; i < 2; i++) {
         numberIsPrime[i] = 0;
      }

      // mark the remaining numbers in the array according to the algo.
      for (unsigned int index = 2; index < maxFactor;) {
         // mark all of multiples that can't be prime
         for (unsigned int nonPrimeIndex = (2 * index);
              nonPrimeIndex < (limit + 1); nonPrimeIndex += index) {
            numberIsPrime[nonPrimeIndex] = 0;
         }

         // adjust the index
         do {
            index++;
            if (numberIsPrime[index]) {
               break;
            }
         } while (index <= maxFactor);
      }
      // collect and count the primes found
      for (unsigned int i = 1; i < limit + 1; i++) {
         if (numberIsPrime[i]) {
            primes[numberOfPrimes++] = i;
         }
      }
      free(numberIsPrime);
   }
   return numberOfPrimes;
}

Version data entries

132 entries across 132 versions & 1 rubygems

Version	Path
trackler-2.2.1.45	tracks/c/exercises/sieve/src/example.c
trackler-2.2.1.44	tracks/c/exercises/sieve/src/example.c
trackler-2.2.1.43	tracks/c/exercises/sieve/src/example.c
trackler-2.2.1.42	tracks/c/exercises/sieve/src/example.c
trackler-2.2.1.41	tracks/c/exercises/sieve/src/example.c
trackler-2.2.1.40	tracks/c/exercises/sieve/src/example.c
trackler-2.2.1.39	tracks/c/exercises/sieve/src/example.c
trackler-2.2.1.38	tracks/c/exercises/sieve/src/example.c
trackler-2.2.1.37	tracks/c/exercises/sieve/src/example.c
trackler-2.2.1.36	tracks/c/exercises/sieve/src/example.c
trackler-2.2.1.35	tracks/c/exercises/sieve/src/example.c
trackler-2.2.1.34	tracks/c/exercises/sieve/src/example.c
trackler-2.2.1.33	tracks/c/exercises/sieve/src/example.c
trackler-2.2.1.32	tracks/c/exercises/sieve/src/example.c
trackler-2.2.1.31	tracks/c/exercises/sieve/src/example.c
trackler-2.2.1.30	tracks/c/exercises/sieve/src/example.c
trackler-2.2.1.29	tracks/c/exercises/sieve/src/example.c
trackler-2.2.1.28	tracks/c/exercises/sieve/src/example.c
trackler-2.2.1.27	tracks/c/exercises/sieve/src/example.c
trackler-2.2.1.26	tracks/c/exercises/sieve/src/example.c