Eratosthene's sieve is an ancient way to list all prime numbers by
starting with a list of all numbers and then repeatedly removing
the multiples of each prime as it is found:
Inititally
{ 2, 3, 4, 5, 6, 7, 8, 9, ...}
and then
{ 2, 3, 5, 7, 9, ...}
{ 2, 3, 5, 7, ...}
and so on.
Professor Hoare pointed out that this could be re-expressed as a
collection of concurent objects. The first generates the natural numbers
greater than equal to 2. The next object filters out even numbers
greater than 2. The next sieves out the multiples of 3, the next
removes multiples
of 5 and so on. The pipeline looks like this Data Flow Diagram:
generate->remove even->remove multiples of 3->remove multiples of 5->..
Notice that each 'remove' object first inputs a prime number (2,3,5,...)
and then uses it to remove multiples. This gives us a very simple
algorithm for each "remove" process:
To remove multiples of a prime
(1): Wait for a your prime number p
(2): Loop
(2.1): wait for a number n
(2.2): if n is not a multiple of p
then send it to the next process
(end if)
(end loop)
In effect each process is a prime number!