# Parallel Sieve of Eratosthenes

Discussion in 'NZ Computing' started by Lawrence D'Oliveiro, Nov 14, 2009.

1. ### Lawrence D'OliveiroGuest

In Algol 68. The parent thread spits out a sequence of integers. Each child
thread takes the first integer itâ€™s given as a prime, outputs it as such,
spawns its own child, and passes it all subsequent integers that are not
multiples of that first one.

Note the PAR clauses for parallel execution of the constituent statements.
Also note the use of semaphores (nowadays considered too low-level and

----
MODE BUFFER = STRUCT
(
SEMA full,
SEMA empty,
REF INT n
);

PROC produce = (BUFFER b, INT n) VOID :
BEGIN
DOWN empty OF b;
n OF b := n;
UP full OF b
END;

PROC consume = (BUFFER b) INT :
BEGIN
DOWN full OF b;
INT n = n OF b;
UP empty OF b;
n
END;

PROC sieve = (BUFFER b1) VOID :
BEGIN
INT n = consume(b1);
print((" => ", n, new line));
BUFFER b2 = (LEVEL 0, LEVEL 1, HEAP INT);
PAR BEGIN
DO
INT i = consume(b1);
IF i MOD n /= 0 THEN
produce(b2, i)
FI
OD,
sieve(b2)
END
END;

BEGIN
BUFFER b = (LEVEL 0, LEVEL 1, HEAP INT);
INT n := 1;
PAR BEGIN
DO
n := n + 1;
produce(b, n)
OD,
sieve(b)
END
END

Lawrence D'Oliveiro, Nov 14, 2009