Want more features on Pastebin? Sign Up, it's FREE!
Guest

prime-sieve.c

By: a guest on Nov 27th, 2013  |  syntax: C  |  size: 1.89 KB  |  views: 34  |  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. /*      The purpose of this program is to list the first N prime
  2.         numbers on the standard output.  Uses the Sieve of
  3.         Eratosthenes.
  4.  
  5.         Written by Hal Canary, 2010
  6.  
  7.         Compile with:
  8.                 cc -o prime-sieve prime-sieve.c
  9. */
  10. #include <stdio.h>
  11. #include <stdlib.h>
  12. #include <math.h>
  13.  
  14. /* These two macros allow addressing of a particular bit inside of a
  15.    large unsigned char array. */
  16. #define bit_is_true(ARRAY, INDEX) \
  17.   (((ARRAY) [(INDEX)/8] >> ((INDEX) % 8)) & 1)
  18. #define set_bit_true(ARRAY, INDEX) \
  19.   ((ARRAY)[(INDEX) >> 3] |= (1 << ((INDEX) & 7)))
  20. /* And for completeness */
  21. #define set_bit_false(ARRAY, INDEX)                                     \
  22.   ((ARRAY)[(INDEX) >> 3] &= ~(1 << ((INDEX) & 7)))
  23.  
  24. int main(int argc, char *argv[]) {
  25.   unsigned int maxprime = 0; /* the number of numbers to test for primeness. */
  26.   unsigned int test;    /* the number currently being tested for primeness */
  27.   unsigned int multiple;   /* a composite */
  28.   unsigned char *isprimes;  /* array of primes we have found so far. */
  29.   unsigned int numprimes = 0;   /* How many primes we have found. */
  30.   if (argc == 2) {
  31.     maxprime = atoi(argv[1]);
  32.   }
  33.   if (maxprime == 0) {
  34.     fprintf(stderr,"Usage: primus MAXPRIME\n");
  35.     exit(1);
  36.   }
  37.   int size = (maxprime/8)+1;
  38.   isprimes = malloc(size * sizeof(*isprimes));
  39.   if (isprimes == NULL) {
  40.     fprintf(stderr,"Can't allocate enough memory for that sieve.\n");
  41.     exit(1);
  42.   }
  43.   for (test = 0; test < size; test++) {
  44.     isprimes[test] = 0; /* may be a prime. */
  45.   }
  46.   int x;
  47.   for (test = 2; test <= maxprime; test++) {
  48.     if (bit_is_true(isprimes, test)) /* test is composite */
  49.       continue;
  50.     printf("%i\n",test);
  51.     numprimes++;
  52.     /* test is a prime */
  53.     for (multiple = (test * test); multiple <= maxprime; multiple += test)
  54.       set_bit_true(isprimes, multiple);
  55.   }
  56.   fprintf(stderr,"Between 2 and %i there are %i primes.\n",
  57.           maxprime, numprimes);
  58.   return 0;
  59. }
clone this paste RAW Paste Data