/**************************************************************************
 *
 * Filename:
 *
 *   sieve.c
 *
 * Description:
 *
 *   The Sieve of Eratosthenes benchmark, from Byte Magazine
 *   early 1980s, when a PC would do well to run this in 10 
 *   seconds. This version really does count prime numbers
 *   but omits the numbers 1, 3 and all even numbers. The
 *   expected count is 1899.
 *
 * Revision:
 *
 *   $Id:$
 *
 **************************************************************************/

#include <time.h>
#include <report.h>


#define SIZE 8190

int
sieve ()
{
  unsigned char flags [SIZE + 1];
  int iter; 
  int count;

  for (iter = 1; iter <= 10; iter++) 
    {
      int i, prime, k;

      count = 0;

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

      for (i = 0; i <= SIZE; i++) 
        {
          if (flags [i]) 
            {
              prime = i + i + 3;
              k = i + prime;

              while (k <= SIZE)
                {
                  flags [k] = 0;
                  k += prime;
                }

              count++;
            }
        }
    }

  return count;
}

int
main ()
{
  int ans;
  clock_t t1, t2;

  test ("sieve", "Sieve benchmark, $Revision: 1.1 $");

  t1 = clock ();
  ans = sieve ();
  t2 = clock ();

  if (ans != 1899)
    failed ("Sieve result wrong, ans = %d, expected 1899", ans);

  comment ("Time taken = %.3e mSecs", 
    1000.0 * ((double)t2 - (double)t1) / (double)CLOCKS_PER_SEC);

  result ();
}