/* sieve code -- simple prime number sieve (Sieve of Erathosthenes)
 *
 * CMU 18-548
 */

#include <stdio.h>
/* #define DEBUG */

#define SIZE 159311

#define sieve() doit()   /* for instrumentation purposes */

#define TRUE 1
#define FALSE 0

int sieve()  /* return number of primes found, including the number 1 */
{
  char flags[SIZE];
     /* could optimize by storing only odd numbers, but don't bother */
  long i, j;
  long count=1;  /* include 1 as the first prime found */

  flags[0] = FALSE;
  for (i = 1; i < SIZE; i++)  flags[i] = TRUE;

  for (i = 2; i < SIZE; i++)
  { if (flags[i])
    { /* found a prime -- knock out all multiples of it */
      count++;
      for (j = i + i; j < SIZE; j += i) flags[j] = FALSE;
    }
  }
#ifdef DEBUG
  for (i = 0; i < SIZE; i++)
  { if (flags[i])  printf("%d ", i); }
#endif

  return(count);
}

void main(void)
{ int count;

  printf("> Starting...\n");
  count = sieve();

  printf("> %d Primes found\n", count);

}