<div><blockquote class="gmail_quote" style="margin-top: 0; margin-right: 0; margin-bottom: 0; margin-left: 0; margin-left: 0.80ex; border-left-color: #cccccc; border-left-width: 1px; border-left-style: solid; padding-left: 1ex">
The point about "Eratosthenes's sieve" is that it does not specify<br>algorithmically how to find the next number to be crossed. It does not<br>even define how to store (crossed) numbers, it stores them "on paper".
</blockquote><div><br>But , I believe that Eratosthenes's sieve does specify how to store numbers and how to find the next to cross out.<br><br>This is how I remember it:<br><br>0 List the numbers from 2 onwards.<br>1 Take first uncrossed number, say p.
<br>2 Cross every pth number from there on (crossed or not).<br></div>3 Repeat from 1.<br><br>That "crossed or not" appears above makes repeated filters very tricky. It is trivial with a mutable array, but that is not the preferred way so one needs to somehow merge the crossing out lists. I haven't looked at it really, but being sorted lists I would have thought that this merger would be easy without resorting to things like priority queues, could someone point this out to me?
<br><br>The above mayeasily be optimised to only listing odd numbers (still cross out every pth number in the list), and much less importantly by starting from whereever p*p is.<br></div><br>Jens<br><br>