Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /* 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;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement