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

to extract the program.notangle -R'program to print the first thousand prime numbers'

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 firstend.`m`

prime numbers>

Defines`print_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 first`m`

prime numbers>=(<-U)<fill table;`p`

with the first`m`

prime numbers><print table`p`

>

How should table `p`

be represented?
Two possibilities suggest themselves: We could construct a
sifficiently large aray of boolean values in whith the *k*th entry is
`true`

if and only if the number *k* is prime; or we could build an
array of integers in which the *k*th entry is the *k*th 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
*k*th 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;

Defines`page_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 table`p`

with the first`m`

prime numbers>=(<-U)<initialize the data structures>while k < m do begin<increasek := k + 1; p[k] := j; end`j`

until it is the next prime number>

<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 }

<increase`j`

until it is the next prime number>=(<-U)repeat j := j + 2;<update variables that depend on;`j`

><give tountil j_prime`j_prime`

the meaning:`j`

is a prime number>

<variables of the program>+=(<-U)[<-D->]j_prime: boolean;

Defines`j_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 }

Defines`ord`

,`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 on`j`

>=(<-U)if j = square then begin ord := ord + 1;<update variables that depend onend`ord`

>

<update variables that depend on`ord`

>=(<-U)[D->]square := p[ord] * p[ord]; { at this point ord <= k }

<give to`j_prime`

the meaning:`j`

is a prime number>=(<-U)n := 2; j_prime := true; while (n < ord) and j_prime do begin<if; n := n + 1; end`p[n]`

is a factor of`j`

, set`j_prime := false`

>

<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 }

Defines`mult`

(links are to index).

<update variables that depend on`ord`

>+=(<-U)[<-D]mult[ord-1] := j;

<if`p[n]`

is a factor of`j`

, set`j_prime := false`

>=(<-U)while mult[n] < j do mult[n] := mult[n] + p[n] + p[n]; if mult[n] = j then j_prime := false;

*<*>*: D1*<fill table*: U1, D2`p`

with the first`m`

prime numbers>*<give to*: U1, D2`j_prime`

the meaning:`j`

is a prime number>*<if*: U1, D2`p[n]`

is a factor of`j`

, set`j_prime := false`

>*<increase*: U1, D2`j`

until it is the next prime number>*<initialize the data structures>*: U1, D2, D3*<other constants of the program>*: U1, D2, D3*<output a line of answers>*: U1, D2*<output a page of answers>*: U1, D2*<print table*: U1, D2`p`

>*<print the first*: U1, D2`m`

prime numbers>*<program to print the first thousand prime numbers>*: U1, D2*<update variables that depend on*: U1, D2`j`

>*<update variables that depend on*: U1, D2, D3`ord`

>*<variables of the program>*: U1, D2, D3, D4, D5, D6, D7, D8

- j_prime: U1, D2, U3, U4
- mult: D1, U2, U3
- ord: D1, U2, U3, U4, U5, U6, U7
- page_number: D1, U2, U3
- page_offset: D1, U2, U3
- print_primes: D1
- row_offset: D1, U2, U3
- square: D1, U2, U3, U4

**[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.