prime-sieve.c

/*  The purpose of this program is to list the first N prime
    numbers on the standard output.  Uses the Sieve of
    Eratosthenes.

    Written by Hal Canary, 2010

    Compile with:
        cc -o prime-sieve prime-sieve.c
*/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

/* These two macros allow addressing of a particular bit inside of a
   large unsigned char array. */
#define bit_is_true(ARRAY, INDEX) \
  (((ARRAY) [(INDEX)/8] >> ((INDEX) % 8)) & 1)
#define set_bit_true(ARRAY, INDEX) \
  ((ARRAY)[(INDEX) >> 3] |= (1 << ((INDEX) & 7)))
/* And for completeness */
#define set_bit_false(ARRAY, INDEX)                 \
  ((ARRAY)[(INDEX) >> 3] &= ~(1 << ((INDEX) & 7)))

int main(int argc, char *argv[]) {
  unsigned int maxprime = 0; /* the number of numbers to test for primeness. */
  unsigned int test;    /* the number currently being tested for primeness */
  unsigned int multiple;   /* a composite */
  unsigned char *isprimes;  /* array of primes we have found so far. */
  unsigned int numprimes = 0;   /* How many primes we have found. */
  if (argc == 2) {
    maxprime = atoi(argv[1]);
  }
  if (maxprime == 0) {
    fprintf(stderr,"Usage: primus MAXPRIME\n");
    exit(1);
  }
  int size = (maxprime/8)+1;
  isprimes = malloc(size * sizeof(*isprimes));
  if (isprimes == NULL) {
    fprintf(stderr,"Can't allocate enough memory for that sieve.\n");
    exit(1);
  }
  for (test = 0; test < size; test++) {
    isprimes[test] = 0; /* may be a prime. */
  }
  int x;
  for (test = 2; test <= maxprime; test++) {
    if (bit_is_true(isprimes, test)) /* test is composite */
      continue;
    printf("%i\n",test);
    numprimes++;
    /* test is a prime */
    for (multiple = (test * test); multiple <= maxprime; multiple += test)
      set_bit_true(isprimes, multiple);
  }
  fprintf(stderr,"Between 2 and %i there are %i primes.\n",
      maxprime, numprimes);
  return 0;
}