/* Sieve of Eratosthenes in ANSI C.
* By Dr Frankenstein
* 2009-08-15 */
/* Call the program with a positive integer as parameter, and it'll print a
* list of primes up to that number. */
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
/* We'll use a doubly-linked list for easy element deletion. */
struct number
{
unsigned value;
struct number* next,
* prev;
}* sieve = NULL;
/* Create a sieve with range [2..limit] */
void fill_sieve(unsigned limit)
{
size_t offset;
struct number* prev = NULL;
/* Try to allocate memory for the sieve. */
/* It IS a contiguous array, however we want linked list properties
for easy deletion. */
sieve = calloc(limit, sizeof(struct number));
if(!sieve) abort(); /* FAIL! */
/* For each index from [0..limit-2]... */
for(offset = 0; offset <= limit - 2; offset++)
{ /* ...assign a sieve element with proper pointers. */
sieve[offset].value = offset + 2;
sieve[offset].prev = prev;
sieve[offset].next = sieve + (offset + 1);
prev = sieve + offset;
}
sieve[offset].next = NULL; /* End of list */
}
/* Delete an element from the sieve. */
void delete_number(struct number* num)
{ /* Cut and splice the list. */
num->prev->next = num->next;
if(num->next)
/* Only work with our neighbour if it actually exists... */
num->next->prev = num->prev;
/* DO NOT free()! (the whole list was alloc'd in one shot) */
}
int main(int argc, char* argv[])
{
unsigned limit, stop;
struct number* base, * cur;
/* Take the sieve's upper limit as argument. */
if(argc != 2)
{
puts("Usage: sieve <limit>\n");
return EXIT_FAILURE;
}
limit = strtoul(argv[1], NULL, 10);
/* Create the list. */
fill_sieve(limit);
/* We use a variable to avoid recalculating the sqrt at each iteration.
As far as I know, only GCC optimizes this away because of
__attribute__((const)) */
stop = (unsigned) sqrt(limit);
/* For each number in [2..sqrt(limit)]... */
for(base = sieve; base->value <= stop; base = base->next)
{
struct number* num = base;
/* ...remove every multiple of that number. */
while(num = num->next)
{
if(!(num->value % base->value))
{
delete_number(num);
}
}
}
/* Show. */
for(cur = sieve; cur; cur = cur->next)
{
printf("%u, ", cur->value);
}
putchar('\n');
return EXIT_SUCCESS;
}