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.