Prime number generator

[bryanjugglercryptographer at yahoo.com]

Chris Angelico wrote:
> Bas wrote:
> > Still trying to figure out your algorithm ...
> 
> It's pretty simple. (That's a bad start, I know!) Like the Sieve of
> Eratosthenes, it locates prime numbers, then deems every multiple of
> them to be composite. Unlike the classic sieve, it does the "deem"
> part in parallel. Instead of marking all the multiples of 2 first,
> then picking three and marking all the multiples of 3, then 5, etc,
> this function records the fact that it's up to (say) 42 in marking
> multiples of 2, and then when it comes to check if 43 is prime or not,
> it moves to the next multiple of 2. This requires memory to store the
> previously-known primes, similarly to other methods, but needs no
> multiplication or division.

Knuth points to the method, using a priority queue, in exercise 15 of section 5.2.3 of /Sorting and Searching/, and credits it to "B. A. Chartres".

-- 
-Bryan