EWD249 - 48

of which we can store multiples of the successive prime numbers, as close to j as is convenient. In order to be able to give the size of the array we should like to know an upper bound for the value of ord; of course, 1000 would be safe, but number theory gives us 30 as a safe upper bound. We therefore introduce

integer array mult[1:30]

and introduce the convention that for n < ord, mult[n] will be a multiple of p[n] and will satisfy the relation

            mult[n] < j + p[n]

a relation that remains invariantly true under increase of j. Whenever we wish to investigate, whether p[n] is a factor of j, we increase mult[n] by p[n] as long as mult[n] < j .

After this increase mult[n] = j is the necessary and sufficient condition for j to be a multiple of p[n].

The low maximum value of ord has another consequence: the inspection "ord too small" can be expressed by

                   "p[ord] ↑ 2 ≤ j"

but this inspection has to be performed many times for the same value of ord. We may assume that we can speed up matters by introducing a variable (called "square") whose value equals p[ord] ↑ 2 .

So we come to our final

level 2b5(4):
integer square; integer array mult[1:30];
2b4(4)a   =
begin ord:= 1; square:= 4 end;
2b4(4)b   =
      (square ≤ j);
2b4(4)c   =
begin mult[ord]:= square; ord:= ord + 1; square:= p[ord] ↑ 2 end;
2b4(4)d   =
begin while mult[n] < j do mult[n]:= mult[n] + p[n]; r:= j - mult[n] end

which has made our computation close to an implementation of the Sieve of Eratosthenes!