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 -- http://mail.python.org/mailman/listinfo/python-list
