keithd@cadovax.UUCP (Keith Doyle) (11/13/84)
Has anyone noticed that the original BYTE article and all of the
followups on the Sieve of Eras... (forgot how to spell it) Primes
program have been perpetuating a BUG? At one time, I wanted to see
the primes that it generated. The algorithm works by initializing
an array of flags, 1-8192 etc. each used to indicate whether or not
the numbers 1-8192 are prime. The program scans the array, first by
2's and marks all multiples of 2 as non-prime. It then scans the
array for the next prime, 3, and then scans the array by 3's marking
all multiples as non-prime. The original program misses one of these
scans (the first one I think) leaving several non-primes marked as
prime. The count of primes is then incorrect, and this error has
been perpetuated ever since the initial benchmark program was
published. Not that it matters really, I suppose it's still a
reasonable comparison test, but it does give the wrong answer for
the number of primes from 1-8192 (there are 1029).
Keith Doyle
{ucbvax,decvax}!trwrb!cadovax!keithdcdl@mplvax.UUCP (Carl Lowenstein) (11/14/84)
The first prime number is 2 not 1. A prime number has exactly two
distinct positive integer factors. My version of the Byte benchmark
gives 1028 prime numbers between 2 and 8192 inclusive. (Pascal, C,
PDP-11 Macro, ...)
--
carl lowenstein marine physical lab u.c. san diego
{ihnp4|decvax|akgua|dcdwest|ucbvax} !sdcsvax!mplvax!cdlkeithd@cadovax.UUCP (Keith Doyle) (11/15/84)
Information I have recently received indicates that the error in the
Sieve benchmark may not have been introduced until a Dr. Dobbs article
published that referenced the original Byte article. I will research
this and report any specific findings.
Keith Doyle
{ucbvax,ihnp4,decvax}!trwrb!cadovax!keithd
"Be Seeing You!"
--
Keith Doyle
{ucbvax,ihnp4,decvax}!trwrb!cadovax!keithd
"Be Seeing You!"