Here's a slightly unconventional implementation which uses logical time to synchronize threads.

```{- publish primes < n -}
def primes(n) =
{- publish every dth number from i to n, one per
unit of logical time -}
def walk(i, d) =
if i >= n then stop
else Ltimer(1) >> (i | walk(i+d, d))
{- visited non-prime numbers -}
val seen = Set()
2 | walk(3, 2) >i> if(~seen(i)?) >> (
i | walk(i*i, i) >j> seen.add(j) >> stop
)

primes(1000)```

The algorithm is described in Tasking solutions to the Sieve of Eratosthenes. The idea is for one process to walk down the numbers and when it finds a prime number, it reports it and then sends another process forward to mark all multiples of that number as non-prime.

This implementation uses logical time to ensure that the prime-finding process moves more slowly than the prime-removing processes, so any number it visits has already been considered by all the prime-removing processes.

The work complexity is the same as the original Sieve of Eratosthenes: O(n log log n). The time complexity is O(n), since the prime-finding process does not take more than n/2 logical time steps to report all the primes, and each process is independent within each logical time step.

Only authorized users are allowed to upload new attachments.