# [Haskell-cafe] Re: Genuine Eratosthenes sieve [Was: Optimization fun]

Dan Weston westondan at imageworks.com
Wed Feb 21 16:52:56 EST 2007

```I would be interested in seeing a multithreaded solution, with each
child thread crossing off the multiples of its own prime. The parent
thread would be blocked from spawning a new thread for multiples of the
next prime p until all existing child threads are past p.

It is not clear to me what functional data structure would most
efficiently accommodate this algorithm, however. Any suggestions?

Dan Weston

apfelmus at quantentunnel.de wrote:
> 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
>
> _______________________________________________