/*  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;
}