Dijkstra's program prints a table of the first thousand prime numbers. We shall begin as he did, by reducing the entire program to its top-level description.
<*>= <program to print the first thousand prime numbers>
[[Double brackets will be used in what follows to enclose comments relating to noweb itself. This definition of the root module could have been eliminated by choosing to use
notangle -R'program to print the first thousand prime numbers'to extract the program.]]
This program has no input, because we want to keep it simple.
The result of the program will be to produce a list of the first
thousand prime numbers, and this list will appear on the output
file.
Since there is no input, we declare the value m = 1000
as a
compile-time constant.
The program itself is capable of generating the first m
prime
numbers for any positive m
, as long as the computer's finite
limitations are not exceeded.
<program to print the first thousand prime numbers>= (<-U)
program print_primes(output);
const m = 1000;
<other constants of the program>
var <variables of the program>
begin <print the first m
prime numbers>
end.
Definesprint_primes
(links are to index).
Let us decide at this point to maintain a table that includes all of the prime numebrs that will be generated, and to sepaerate the genreation problem from the printing problem.
<print the firstm
prime numbers>= (<-U) <fill tablep
with the firstm
prime numbers>; <print tablep
>
How should table p
be represented?
Two possibilities suggest themselves: We could construct a
sifficiently large aray of boolean values in whith the kth entry is
true
if and only if the number k is prime; or we could build an
array of integers in which the kth entry is the kth prime number.
Let us choose the latter alternatice, by introducing an intereger
array called p[1..m]
.
In the documentation below, the notation p[k]
will refer to the
k
th element of the array p
, while p_k will refer to the
kth prime number.
If the program is correct p[k]
will equal p_k or it will not yet
have nbeen asigned any value.
<variables of the program>= (<-U) [D->] p: array [1..m] of integer; { the first m prime numbers, in increasing order }
<other constants of the program>= (<-U) [D->] rr = 50; cc = 4; ww = 10;
<variables of the program>+= (<-U) [<-D->] page_number: integer; page_offset: integer; row_offset: integer; c: 0..cc;
Definespage_number
,page_offset
,row_offset
(links are to index).
<print table p
>= (<-U)
begin page_number := 1; page_offset := 1;
while page_offset <= m do
begin <output a page of answers>;
page_number := page_number + 1;
page_offset := page_poffset + rr * cc;
end;
end
<output a page of answers>= (<-U) begin write('The First '); write(m:1); write(' Prime Numbers --- Page '); write(page_number:1); write_ln; write_ln; { there's a blank line after the heading } for row_offset := pages_offset to page_offset + rr - 1 do <output a line of answers>; page; end
<output a line of answers>= (<-U) begin for c := 0 to cc - 1 do if for_offset + c * rr <= m then write(p[row_offset + c * rr]); writeln; end
<fill tablep
with the firstm
prime numbers>= (<-U) <initialize the data structures> while k < m do begin <increasej
until it is the next prime number> k := k + 1; p[k] := j; end
<variables of the program>+= (<-U) [<-D->] j: integer; { all primes <= j are in table p } k: 0..m; { this many primes are in table p }
<increasej
until it is the next prime number>= (<-U) repeat j := j + 2; <update variables that depend onj
>; <give toj_prime
the meaning:j
is a prime number> until j_prime
<variables of the program>+= (<-U) [<-D->] j_prime: boolean;
Definesj_prime
(links are to index).
<initialize the data structures>= (<-U) [D->] j := 1; k := 1; p[1] := 2;
<variables of the program>+= (<-U) [<-D->] ord: 2..ord_max; { the smallest index >= 2 such that p_ord squared > j } square: integer; { square = p_ord squared }
Definesord
,square
(links are to index).
<initialize the data structures>+= (<-U) [<-D] ord := 2; square := 9;
<other constants of the program>+= (<-U) [<-D] ord_max = 30; { p_ord_max squared must exceed p_m }
<update variables that depend onj
>= (<-U) if j = square then begin ord := ord + 1; <update variables that depend onord
> end
<update variables that depend on ord
>= (<-U) [D->]
square := p[ord] * p[ord]; { at this point ord <= k }
<give toj_prime
the meaning:j
is a prime number>= (<-U) n := 2; j_prime := true; while (n < ord) and j_prime do begin <ifp[n]
is a factor ofj
, setj_prime := false
>; n := n + 1; end
<variables of the program>+= (<-U) [<-D->] n: 2..ord_max; { runs from 2 to ord when testing divisibility }
<variables of the program>+= (<-U) [<-D] mult: array [2..ord_max] of integer; { runs through multiples of primes }
Definesmult
(links are to index).
<update variables that depend on ord
>+= (<-U) [<-D]
mult[ord-1] := j;
<ifp[n]
is a factor ofj
, setj_prime := false
>= (<-U) while mult[n] < j do mult[n] := mult[n] + p[n] + p[n]; if mult[n] = j then j_prime := false;
p
with the first m
prime numbers>: U1, D2
j_prime
the meaning: j
is a prime number>: U1, D2
p[n]
is a factor of j
, set j_prime := false
>: U1, D2
j
until it is the next prime number>: U1, D2
p
>: U1, D2
m
prime numbers>: U1, D2
j
>: U1, D2
ord
>: U1, D2, D3
[1] Donald E. Knuth. Literate programming. The Computer Journal, 27(2):97--111, 1984.
[2] Ole-Johan Dahl, Edsger W. Dijkstra, and C. A. R. Hoare. Structured Programming. Academic Press, London and New York, 1972.