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