[net.micro.cbm] Seive of Erasthones Correection

stephenc@tektronix.UUCP (Stephen Coan ) (10/31/84)

A recently posted article had a 'C' program for the Seive.  It appears that
the program was one that came from BYTE a few years ago.  The program is
fine for benchmarks, but is HORRIBLE as a real seive.  Take a look at the 
output, and you will see prime numbers such as 6242, etc.  A corrected
version of the program follows:

#define SIZE 8191

char flags[SIZE];

main()
{
	short i, prime, k, count;	/* short for portability */

	count = 0;
	for (i = 0; i < SIZE; i++)
		flags[i] = 1;
	for (i = 2; i < SIZE; i++)	{
		if (flags[i])	{
			prime = i;
			for (k = prime + prime; k < SIZE; k += prime)
				flags[k] = 0;
			count++;
			printf ("%d\n",prime);
		}
	}
	printf ("\n%d primes.\n", count);
}
The correct count when run is 1027 primes.
NOTE:  This does not have the 10 iterations included as the did the BYTE
article.  This can be added by those that wish to use it for benchmark
testing.  

	I hope that this will help to clear up some possible confusion that
was generated by the BYTE article since it was published.  Happy computing!

			The Novice Unix Hacker
			Stephen Coan
			tektronix!scargo!stephenc