# 5.1 Sieve of Eratosthenes

The problem here is to find all the prime numbers less than or equal
to *k*. We do it with a Felix "circuit" of fibres and
s-channels.

The control token exchanged along the s-channels consists of a number and a list of candidate primes.

typedef il_t = int * list[int];

A client filters multiples of the number from the list to produce a new list and, as long as there's a "next" filtering to apply, spawns a new client for that.

If there aren't any more filterings to be applied, the client transfers control back to the server.

proc client (x:ischannel[il_t], y:oschannel[il_t]) { p, l := read x; l = List::filter (fun (e:int) => (e%p != 0 or e/p == 1)) l; val r = List::find (fun (e:int) => e > p) l; match r with | #None => write$ y, (0, l); //We're done | Some x => inp,out:=#mk_ioschannel_pair[il_t]; spawn_fthread { client (inp, y); }; write$ out, (x, l); endmatch; }

The server seeds the computation by generating a range of integers
from *2..(k + 1)* and spawns a client to filter those that are
multiples of *2*.

proc sieve (k:int) { inp,out:=#mk_ioschannel_pair[il_t]; spawn_fthread { client (inp, out); }; var l = List::range (2, (k + 1)); write$ out, (2, l); val i, res = read inp; println$ "Primes: " + str (res); }

The whole process begins by calling the server with a value for
*k*.

val k = 1000; //Run with FLX_MIN_MEM=500 (MB) for k=5000 sieve k;

For *k = 100* you should observe output something like:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97