Hoare chooses a set type with elements 2 .. n to represent both the sieve and the primes. The following is a slight variation of the program sketch he presents. 

program Prime1; { Program 8.3 - Use sets to implement Sieve of Erastosthenes. const N = 10000; type Positive = 1 .. Maxlnt; var Sieve, Primes: set of .. N; NextPrime, Multiple: P ~;itive; begin {initialize} Sieve := [2 .. N]; Primes:= []; NextPrime:= 2; repeat {find next prim> while not (NextPrime i: Sieve) do NextPrime := Succ(Ne: I Prime); Primes := Primes + [Ne>tPrime]; Multiple := NextPrime; while Multiple <= N do {eliminate begin Sieve:= Sieve - [Multiple]; Multiple := Multipl~ + NextPrime; end until Sieve = [] end . 

As an exercise Hoare proposes rewriting the program, so that the sets only represent the odd numbers. TIle following is one solution. Note the close correlation with the first solution. 

program Prime2; { Program 8.4 - Use sets ,) implement Sieve of Erastosthenes; r·present odd numbers only. const N = 5000 {N' = N div }; type Positive = 1 .. Maxlnt; var Sieve, Primes: set of 2 .. N; NextPrime, Multiple, NewPrime: Positive; 

