# 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])
{
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`