/* finds prime numbers from 2 to N, using the Sieve of Eratosthenes:

   list the numbers from 2 to N; "cross out" all multiples of 2;
   "cross out" all multiples of 3; etc.; the ones remaining are
   the primes */

#define MAX_N 10000

int N,  /* determine the number of primes between 2 and N */
    Composite[MAX_N];  /* in the end, Composite[I] = 1 means I
                          is composite, i.e. nonprime */

void DoSieve(I)  /* does the "crossing out" for multiples of I */
   int I;

{  int J;

   for (J = 2; I*J <=N; J++)
      Composite[I*J] = 1;
}

main()

{  int I,Count;

   N = 100; 

   for (I = 2; I <= N; I++) Composite[I] = 0;

   /* now we can do the "crossing out" for various I, up to the
      square root of N (do a test case "by hand" to see why we
      don't have to go past that point); of course, if we have
      already discovered a given I to be composite, there is no
      point crossing out its multiples, since they will already
      have been crossed out as multiples of some earlier factor
      of I */
   for (I = 2; I*I <= N; I++)
      if (!Composite[I]) DoSieve(I);

   Count = 0;
   for (I = 2; I <= N; I++)
      if (Composite[I]) Count++;

   printf("the number of primes is %d\n",N-Count-1);
}