Das Sieb des Eratosthenes ist ein Verfahren, mit dem Primzahlen bestimmt werden können. Zunächst werden alle natürlichen Zahlen beginnend mit der 2 aufgeschrieben. Die kleinste, nicht markierte Zahl ist eine Primzahl. Das ist als erstes die 2. Dann markiert man alle Vielfachen der 2. Wiederum ist die kleinste, nicht markierte Zahl eine Primzahl: die 3. Man markiert alle Vielfachen der 3 und erhält die 5 und so weiter.

Mit den Primitiven für Kanäle kann man das Verfahren mit vier Bestandteilen umsetzen.

Zunächst erstellt man einen Generator für natürlichen Zahlen ab einem gewissen Limit. Die Zahlen können von einem Kanal empfangen werden.

(defproc next-integers (out current)
  (when
    (send-on-channel out current nil)
    (next-integers out (+ current 1))))

(defproc integer-generator (start)
  (let
    ((out (make-channel 0)))
    (progn
      (go (next-integers out start))
      out)))

Der zweite Bestandteil der Umsetzung ist eine Funktion, die Zahlen von einem Kanal empfängt und auf einem anderen Kanal sendet, es sei denn, es handelt sich um Vielfache einer gegebenen Zahl.

(defproc filter-multiples (in out factor)
  (let
    ((number (receive-from-channels (list in) nil)))
    (if
      (integer? (/ number factor))
      (filter-multiples in out factor)
      (when
        (send-on-channel out number nil)
        (filter-multiples in out factor)))))

Das eigentliche Sieb empfängt eine Zahl von einem Kanal, sendet sie an einen anderen Kanal und schiebt dann den Filter für die Vielfachen der Zahl ein.

(defproc sieve (in out)
  (let
    ((prime (receive-from-channels (list in) nil))
     (transfer (make-channel 0)))
    (when
      (send-on-channel out prime nil)
      (go (filter-multiples in transfer prime))
      (sieve transfer out))))

Der Generator für Primzahlen wendet das Sieb auf einen Kanal an, der alle natürlichen Zahlen ab der 2 liefert.

(defproc prime-generator ()
  (let
    ((out (make-channel 0)))
    (progn
      (go (sieve (integer-generator 2) out))
      out)))