Tuesday, December 30, 2014

Sum of Prime Numbers Between 1000000 and 1000100 Using Sieve of Eratosthenes

NB: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

 
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
#include "assert.h"

typedef  unsigned long long biggerint;

void findPrimeNumbers(biggerint start, biggerint end) {
 char * primeList = malloc(sizeof(unsigned char) * (end + 1));
 int i;
 biggerint sum = 0;

 assert(primeList != NULL);

 /* set prime status */
 for (i = 0; i <= end + 1 ; i++) {
  *(primeList + i) = 1;
 }

 primeList[0] = 0;
 primeList[1] = 0;

 /* mark all the non-prime numbers */
 biggerint currentFactor = 2;
 biggerint lastSquare = 0;
 biggerint currentSquare = 0;
 while (currentFactor * currentFactor <= end) {
  /* mark all the multiples of the current factor */
  biggerint mark = currentFactor + currentFactor;
  while (mark <= end) {
   *(primeList + mark) = 0;
   mark += currentFactor;
  }  

  /* set currentFactor to next prime number */
  currentFactor++;
  while (*(primeList+currentFactor) == 0) currentFactor++;
  assert(currentFactor <= end);
 }

 
 for(i = start; i <= end ; i++) {
  if(*(primeList + i)) sum += i;
 }

 free(primeList);

 printf("%llu\n", sum);
}

int main(int argc, char *argv[]) {
 biggerint start = 1000000;
 biggerint end = 1000100;
 findPrimeNumbers(start, end);
 return 0;
}

0 comments:

Post a Comment

Contact Form

Name

Email *

Message *