Jens Blanck wrote:
The point about "Eratosthenes's sieve" is that it does not specify algorithmically how to find the next number to be crossed. It does not even define how to store (crossed) numbers, it stores them "on paper".
But , I believe that Eratosthenes's sieve does specify how to store numbers and how to find the next to cross out.
This is how I remember it:
0 List the numbers from 2 onwards. 1 Take first uncrossed number, say p. 2 Cross every pth number from there on (crossed or not). 3 Repeat from 1.
And where's the storage specification? :) What I'd like to say is that in step 0, "list the numbers" may mean many things to the computer. For example, it can list them in a plain list or a finite map or a priority queue (or an array for the imperative). Yitzchaks 'deleteOrd' sieve uses a plain list whereas Melissa stores the crossed numbers in a priority queue. The choice has impact on how fast you can find the next number to be crossed: Yitzchak needs linear time whereas Melissa can do in logarithmic time. Here, time is parametrized by the count of primes smaller than the current number considered. In the end, the computer needs a more detailed description than the human who can see and cross numbers on a piece of paper at his choice. Regards, apfelmus