The Array Method (Sieve of Eratosthenes) in C


#include 
#include
#include
#include

typedef unsigned long long bignum;

void printPrime(bignum bn)
{
static char buf[1000];

sprintf(buf, "%ull", bn);
buf[strlen(buf) - 2] = '\0';
printf("%s\n", buf);
}

void findPrimes(bignum topCandidate)
{
char * array = malloc(sizeof(unsigned char) * (topCandidate + 1));
assert(array != NULL);

/* SET ALL BUT 0 AND 1 TO PRIME STATUS */
int ss;
for(ss = 0; ss <= topCandidate+1; ss++)
*(array + ss) = 1;
array[0] = 0;
array[1] = 0;

/* MARK ALL THE NON-PRIMES */
bignum thisFactor = 2;
bignum lastSquare = 0;
bignum thisSquare = 0;
while(thisFactor * thisFactor <= topCandidate)
{
/* MARK THE MULTIPLES OF THIS FACTOR */
bignum mark = thisFactor + thisFactor;
while(mark <= topCandidate)
{
*(array + mark) = 0;
mark += thisFactor;
}

/* PRINT THE PROVEN PRIMES SO FAR */
thisSquare = thisFactor * thisFactor;
for(;lastSquare < thisSquare; lastSquare++)
{
if(*(array + lastSquare)) printPrime(lastSquare);
}

/* SET thisFactor TO NEXT PRIME */
thisFactor++;
while(*(array+thisFactor) == 0) thisFactor++;
assert(thisFactor <= topCandidate);
}

/* PRINT THE REMAINING PRIMES */
for(;lastSquare <= topCandidate; lastSquare++)
{
if(*(array + lastSquare)) printPrime(lastSquare);
}
free(array);
}

int main(int argc, char *argv[])
{
bignum topCandidate = 1000;
if(argc > 1)
topCandidate = atoll(argv[1]);
findPrimes(topCandidate);
return 0;
}

No comments:

Post a Comment