C   27

sieve.c

Guest on 15th January 2022 09:16:55 AM

  1. /* sieve code -- simple prime number sieve (Sieve of Erathosthenes)
  2.  *
  3.  * CMU 18-548
  4.  */
  5.  
  6. #include <stdio.h>
  7. /* #define DEBUG */
  8.  
  9. #define SIZE 159311
  10.  
  11. #define sieve() doit()   /* for instrumentation purposes */
  12.  
  13. #define TRUE 1
  14. #define FALSE 0
  15.  
  16. int sieve()  /* return number of primes found, including the number 1 */
  17. {
  18.   char flags[SIZE];
  19.      /* could optimize by storing only odd numbers, but don't bother */
  20.   long i, j;
  21.   long count=1;  /* include 1 as the first prime found */
  22.  
  23.   flags[0] = FALSE;
  24.   for (i = 1; i < SIZE; i++)  flags[i] = TRUE;
  25.  
  26.   for (i = 2; i < SIZE; i++)
  27.   { if (flags[i])
  28.     { /* found a prime -- knock out all multiples of it */
  29.       count++;
  30.       for (j = i + i; j < SIZE; j += i) flags[j] = FALSE;
  31.     }
  32.   }
  33. #ifdef DEBUG
  34.   for (i = 0; i < SIZE; i++)
  35.   { if (flags[i])  printf("%d ", i); }
  36. #endif
  37.  
  38.   return(count);
  39. }
  40.  
  41. void main(void)
  42. { int count;
  43.  
  44.   printf("> Starting...\n");
  45.   count = sieve();
  46.  
  47.   printf("> %d Primes found\n", count);
  48.  
  49. }

Raw Paste


Login or Register to edit or fork this paste. It's free.