Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

Dr Frankenstein

By: a guest on Aug 15th, 2009  |  syntax: C  |  size: 2.63 KB  |  views: 1,079  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. /*  Sieve of Eratosthenes in ANSI C.
  2.  *  By Dr Frankenstein
  3.  *  2009-08-15 */
  4.  
  5. /* Call the program with a positive integer as parameter, and it'll print a
  6.  * list of primes up to that number. */
  7.  
  8. #include <stdlib.h>
  9. #include <stdio.h>
  10. #include <math.h>
  11.  
  12. /* We'll use a doubly-linked list for easy element deletion. */
  13. struct number
  14. {
  15.     unsigned        value;
  16.     struct number*  next,
  17.                  *  prev;
  18. }* sieve = NULL;
  19.  
  20. /* Create a sieve with range [2..limit] */
  21. void fill_sieve(unsigned limit)
  22. {
  23.     size_t offset;
  24.     struct number* prev = NULL;
  25.  
  26.     /* Try to allocate memory for the sieve. */
  27.     /* It IS a contiguous array, however we want linked list properties
  28.         for easy deletion. */
  29.     sieve = calloc(limit, sizeof(struct number));
  30.     if(!sieve) abort(); /* FAIL! */
  31.  
  32.     /* For each index from [0..limit-2]... */
  33.     for(offset = 0; offset <= limit - 2; offset++)
  34.     {   /* ...assign a sieve element with proper pointers. */
  35.         sieve[offset].value = offset + 2;
  36.         sieve[offset].prev = prev;
  37.         sieve[offset].next = sieve + (offset + 1);
  38.         prev = sieve + offset;
  39.     }
  40.     sieve[offset].next = NULL;  /* End of list */
  41. }
  42.  
  43. /* Delete an element from the sieve. */
  44. void delete_number(struct number* num)
  45. {   /* Cut and splice the list. */
  46.     num->prev->next = num->next;
  47.     if(num->next)
  48.         /* Only work with our neighbour if it actually exists... */
  49.         num->next->prev = num->prev;
  50.  
  51.     /* DO NOT free()! (the whole list was alloc'd in one shot) */
  52. }
  53.  
  54. int main(int argc, char* argv[])
  55. {
  56.     unsigned limit, stop;
  57.     struct number* base, * cur;
  58.  
  59.     /* Take the sieve's upper limit as argument. */
  60.     if(argc != 2)
  61.     {
  62.         puts("Usage: sieve <limit>\n");
  63.         return EXIT_FAILURE;
  64.     }
  65.     limit = strtoul(argv[1], NULL, 10);
  66.  
  67.     /* Create the list. */
  68.     fill_sieve(limit);
  69.     /* We use a variable to avoid recalculating the sqrt at each iteration.
  70.         As far as I know, only GCC optimizes this away because of
  71.             __attribute__((const)) */
  72.     stop = (unsigned) sqrt(limit);
  73.  
  74.     /* For each number in [2..sqrt(limit)]... */
  75.     for(base = sieve; base->value <= stop; base = base->next)
  76.     {
  77.         struct number* num = base;
  78.         /* ...remove every multiple of that number. */
  79.         while(num = num->next)
  80.         {
  81.             if(!(num->value % base->value))
  82.             {
  83.                 delete_number(num);
  84.             }
  85.         }
  86.     }
  87.  
  88.     /* Show. */
  89.     for(cur = sieve; cur; cur = cur->next)
  90.     {
  91.         printf("%u, ", cur->value);
  92.     }
  93.     putchar('\n');
  94.  
  95.     return EXIT_SUCCESS;
  96. }