summaryrefslogtreecommitdiff
path: root/web/literateprog/primes.tex
diff options
context:
space:
mode:
authorNorbert Preining <norbert@preining.info>2019-09-02 13:46:59 +0900
committerNorbert Preining <norbert@preining.info>2019-09-02 13:46:59 +0900
commite0c6872cf40896c7be36b11dcc744620f10adf1d (patch)
tree60335e10d2f4354b0674ec22d7b53f0f8abee672 /web/literateprog/primes.tex
Initial commit
Diffstat (limited to 'web/literateprog/primes.tex')
-rw-r--r--web/literateprog/primes.tex555
1 files changed, 555 insertions, 0 deletions
diff --git a/web/literateprog/primes.tex b/web/literateprog/primes.tex
new file mode 100644
index 0000000000..b14a43bae8
--- /dev/null
+++ b/web/literateprog/primes.tex
@@ -0,0 +1,555 @@
+\input webmac
+% limbo material
+\font\ninerm=amr9
+\let\mc=\ninerm % medium caps for names like PASCAL
+\def\WEB{{\tt WEB}}
+\def\PASCAL{{\mc PASCAL}}
+\def\[{\ifhmode\ \fi$[\![$}
+\def\]{$]\!]$\ }
+\def\<{$\langle\,$}
+\def\>{$\,\rangle$}
+\def\Dijk{{2}} % unnecessary when combined with text of paper
+\def\goto{{3}} % ditto
+\hyphenation{Dijk-stra} % ditto
+\def\sec{{\tensy x}}
+\hsize=84mm
+
+
+\N1. Printing primes: An example of \WEB.
+The following program is essentially the same as Edsger Dijkstra's
+``first example of step-wise program composition,''
+found on pages 26--39 of his {\sl Notes on Structured Programming},$^{\Dijk}$
+but it has been translated into the \WEB\ language.
+
+\[Double brackets will be used in what follows to enclose comments
+relating to \WEB\ itself, because the chief purpose of this program
+is to introduce the reader to the \WEB\ style of documentation.
+\WEB\ programs are always broken into small sections, each
+of which has a serial number; the present section is number~1.\]
+
+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. \[Every section in a \WEB\ program begins with optional {\it
+commentary\/} about that section, and ends with optional {\it program
+text\/} for the section. For example, you are now reading part of the
+commentary in \sec1, and the program text for \sec1 immediately follows
+the present paragraph. Program texts are specifications of \PASCAL\
+programs; they either use \PASCAL\ language directly, or they use angle
+brackets to represent \PASCAL\ code that appears in other sections. For
+example, the angle-bracket notation `\X2:Program to print $\ldots$
+numbers\X' is \WEB's way of saying the following: ``The \PASCAL\ text to
+be inserted here is called `Program to print $\ldots$ numbers', and you
+can find out all about it by looking at section~2.'' One of the main
+characteristics of \WEB\ is that different parts of the program are
+usually abbreviated, by giving them such an informal top-level
+description.\]
+
+\Y\P\X2:Program to print the first thousand prime numbers\X\par
+\fi
+
+\M2. This program has no input, because we want to keep it rather 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.
+
+\[The program text below specifies the ``expanded meaning'' of `\X2:Program
+to print $\ldots$ numbers\X'; notice that it involves the top-level
+descriptions of three other sections. When those top-level descriptions
+are replaced by their expanded meanings, a syntactically correct \PASCAL\
+program will be obtained.\]
+
+\Y\P$\4\X2:Program to print the first thousand prime numbers\X\S$\6
+\4\&{program}\1\ \37$\\{print\_primes}(\\{output})$;\6
+\4\&{const} \37$\|m=1000$;\5
+\X5:Other constants of the program\X\6
+\4\&{var} \37\X4:Variables of the program\X\6
+\&{begin} \37\X3:Print the first \|m prime numbers\X;\6
+\&{end}.\par
+\U section~1.\fi
+
+
+\N3. Plan of the program.
+We shall proceed to fill out the rest of the program by making whatever
+decisions seem easiest at each step; the idea will be to strive for
+simplicity first and efficiency later, in order to see where this leads us.
+The final program may not be optimum, but we want it to be reliable,
+well motivated, and reasonably fast.
+
+Let us decide at this point to maintain a table that includes all of the
+prime numbers that will be generated, and to separate the generation
+problem from the printing problem.
+
+\[The \WEB\ description you are reading once again follows a pattern that
+will soon be familiar: A typical section begins with comments and
+ends with program text. The comments motivate and explain noteworthy
+features of the program text.\]
+
+\Y\P$\4\X3:Print the first \|m prime numbers\X\S$\6
+\X11:Fill table \|p with the first \|m prime numbers\X;\6
+\X8:Print table \|p\X\par
+\U section~2.\fi
+
+\M4. How should table \|p be represented? Two possibilities suggest
+themselves: We could construct a sufficiently large array
+of boolean values in which 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 \|kth entry is the \|kth prime number. Let us choose the latter
+alternative, by introducing an integer array called $\|p[1\to\|m]$.
+
+In the documentation below, the notation `$\|p[\|k]$' will refer to the
+\|kth element of array~\|p, while `$p_k$' will refer to the $k$th
+prime number. If the program is correct, $\|p[\|k]$ will either be
+equal to $p_k$ or it will not yet have been assigned any value.
+
+\[Incidentally, our program will eventually make use of several
+more variables as we refine the data structures. All of the sections
+where variables are declared will be called `\X4:Variables of the
+program\X'; the number `{\eightrm4}' in this name refers to the
+present section, which is the first section to specify the
+expanded meaning of `\<Variables of the program\>'.
+The note `{\eightrm See also $\ldots$}' refers to all of the other
+sections that have the same top-level description. The expanded meaning of
+`\X4:Variables of the program\X' consists of all the program texts
+for this name, not just the text found in~\sec4.\]
+
+\Y\P$\4\X4:Variables of the program\X\S$\6
+\4\|p: \37\&{array} $[1\to\|m]$ \1\&{of}\5
+\\{integer};\C{the first \|m prime numbers, in increasing order}\2\par
+\A sections~7, 12, 15, 17, 23, and~24.
+\U section~2.\fi
+
+
+\N5. The output phase.
+Let's work on the second part of the program first. It's not as interesting
+as the problem of computing prime numbers; but the job of printing must be
+done sooner or later, and we might as well do it sooner, since it will
+be good to have it done. \[And it is easier to learn \WEB\ when reading a
+program that has comparatively few distracting complications.\]
+
+Since \|p is simply an array of integers, there is little difficulty
+in printing the output, except that we need to decide upon a suitable
+output format. Let us print the table on separate pages, with \\{rr} rows
+and \\{cc} columns per page, where every column is \\{ww} character positions
+wide. In this case we shall choose $\\{rr}=50$, $\\{cc}=4$, and $\\{ww}=10$, so
+that
+the first 1000 primes will appear on five pages. The program will
+not assume that \|m is an exact multiple of $\\{rr}\cdot\\{cc}$.
+
+\Y\P$\4\X5:Other constants of the program\X\S$\6
+$\\{rr}=50$;\C{this many rows will be on each page in the output}\6
+$\\{cc}=4$;\C{this many columns will be on each page in the output}\6
+$\\{ww}=10$;\C{this many character positions will be used in each column}\par
+\A section~19.
+\U section~2.\fi
+
+\M6. In order to keep this program reasonably free of notations that
+are uniquely \PASCAL esque, \[and in order to illustrate more of the
+facilities of \WEB,\] a few macro definitions for low-level output
+instructions are introduced here. All of the output-oriented commands
+in the remainder of the program will be stated in terms of five
+simple primitives called \\{print\_string}, \\{print\_integer}, \\{print%
+\_entry},
+\\{new\_line}, and \\{new\_page}.
+
+\[Sections of a \WEB\ program are allowed to contain {\it macro definitions\/}
+between the opening comments and the closing program text. The
+general format for each section is actually tripartite: commentary,
+then definitions, then program. Any of the three parts may be absent;
+for example, the present section contains no program text.\]
+
+\[Simple macros simply substitute a bit of \PASCAL\ code for an
+identifier. Parametric macros are similar, but they also substitute
+an argument wherever `\#' occurs in the macro definition. The first three
+macro definitions here are parametric; the other two are simple.\]
+
+\Y\P\D \37$\\{print\_string}(\#)\S\\{write}(\#)$\C{put a given string into the %
+\\{output} file}\par
+\P\D \37$\\{print\_integer}(\#)\S\\{write}(\#:1)$\C{put a given integer into
+the \\{output} file, in decimal notation, using only as many digit
+positions as necessary}\par
+\P\D \37$\\{print\_entry}(\#)\S\\{write}(\#:\\{ww})$\C{like \\{print\_integer},
+but \\{ww} character positions are filled, inserting blanks at the left}\par
+\P\D \37$\\{new\_line}\S\\{write\_ln}$\C{advance to a new line in the %
+\\{output} file}\par
+\P\D \37$\\{new\_page}\S\\{page}$\C{advance to a new page in the \\{output}
+file}\par
+\fi
+
+\M7. Several variables are needed to govern the output process. When we begin
+to print a new page, the variable \\{page\_number} will be the ordinal number
+of that page, and \\{page\_offset} will be such that $\|p[\\{page\_offset}]$ is
+the
+first prime to be printed. Similarly, $\|p[\\{row\_offset}]$ will be the first
+prime in a given row.
+
+\[Notice the notation `$+\S$' below; this indicates that the present
+section has the same name as a previous section, so the program text
+will be appended to some text that was previously specified.\]
+
+\Y\P$\4\X4:Variables of the program\X\mathrel{+}\S$\6
+\4\\{page\_number}: \37\\{integer};\C{one more than the number of pages printed
+so far}\6
+\4\\{page\_offset}: \37\\{integer};\C{index into \|p for the first entry on the
+current page}\6
+\4\\{row\_offset}: \37\\{integer};\C{index into \|p for the first entry in the
+current row}\6
+\4\|c: \37$0\to\\{cc}$;\C{runs through the columns in a row}\par
+\fi
+
+\M8. Now that appropriate auxiliary variables have been introduced, the process
+of outputting table~\|p almost writes itself.
+
+\Y\P$\4\X8:Print table \|p\X\S$\6
+\&{begin} \37$\\{page\_number}\K1$;\5
+$\\{page\_offset}\K1$;\6
+\&{while} $\\{page\_offset}\L\|m$ \1\&{do}\6
+\&{begin} \37\X9:Output a page of answers\X;\6
+$\\{page\_number}\K\\{page\_number}+1$;\5
+$\\{page\_offset}\K\\{page\_offset}+\\{rr}\ast\\{cc}$;\6
+\&{end};\2\6
+\&{end}\par
+\U section~3.\fi
+
+\M9. A simple heading is printed at the top of each page.
+
+\Y\P$\4\X9:Output a page of answers\X\S$\6
+\&{begin} \37$\\{print\_string}(\.{\'The\ First\ \'})$;\5
+$\\{print\_integer}(\|m)$;\6
+$\\{print\_string}(\.{\'\ Prime\ Numbers\ ---\ Page\ \'})$;\5
+$\\{print\_integer}(\\{page\_number})$;\5
+\\{new\_line};\5
+\\{new\_line};\C{there's a blank line after the heading}\6
+\&{for} $\\{row\_offset}\K\\{page\_offset}\mathrel{\&{to}}\\{page\_offset}+%
+\\{rr}-1$ \1\&{do}\5
+\X10:Output a line of answers\X;\2\6
+\\{new\_page};\6
+\&{end}\par
+\U section~8.\fi
+
+\M10. The first row will contain
+$$\hbox{$\|p[1]$, $\|p[1+\\{rr}]$, $\|p[1+2\ast\\{rr}]$, \dots;}$$
+a similar pattern holds for each value of the \\{row\_offset}.
+
+\Y\P$\4\X10:Output a line of answers\X\S$\6
+\&{begin} \37\&{for} $\|c\K0\mathrel{\&{to}}\\{cc}-1$ \1\&{do}\6
+\&{if} $\\{row\_offset}+\|c\ast\\{rr}\L\|m$ \1\&{then}\5
+$\\{print\_entry}(\|p[\\{row\_offset}+\|c\ast\\{rr}])$;\2\2\6
+\\{new\_line};\6
+\&{end}\par
+\U section~9.\fi
+
+
+\N11. Generating the primes.
+The remaining task is to fill table~\|p with the correct numbers.
+Let us do this by generating its entries one at a time: Assuming that
+we have computed all primes that are \|j~or less, we will advance \|j
+to the next suitable value, and continue doing this until the
+table is completely full.
+
+The program includes a provision to initialize the variables in certain
+data structures that will be introduced later.
+
+\Y\P$\4\X11:Fill table \|p with the first \|m prime numbers\X\S$\6
+\X16:Initialize the data structures\X;\6
+\&{while} $\|k<\|m$ \1\&{do}\6
+\&{begin} \37\X14:Increase \|j until it is the next prime number\X;\6
+$\|k\K\|k+1$;\5
+$\|p[\|k]\K\|j$;\6
+\&{end}\2\par
+\U section~3.\fi
+
+\M12. We need to declare the two variables \|j and~\|k that were just
+introduced.
+
+\Y\P$\4\X4:Variables of the program\X\mathrel{+}\S$\6
+\4\|j: \37\\{integer};\C{all primes $\L\|j$ are in table \|p}\6
+\4\|k: \37$0\to\|m$;\C{this many primes are in table \|p}\par
+\fi
+
+\M13. So far we haven't needed to confront the issue of what a prime number
+is. But everything else has been taken care of, so we must delve into
+a bit of number theory now.
+
+By definition, a number is called prime if it is an integer greater
+than~1 that is not evenly divisible by any smaller prime number. Stating
+this another way, the integer $\|j>1$ is not prime if and only if there
+exists a prime number $p_n<j$ such that \|j is a multiple of~$p_n$.
+
+Therefore the section of the program that is called `\<Increase \|j until
+it is the next prime number\>' could be coded very simply:
+`\ignorespaces \&{repeat} $\|j\K\|j+1$;\unskip\
+\<Give to~\\{j\_prime} the meaning: \|j~is a prime number\>;
+\ignorespaces \&{until} \\{j\_prime}\unskip'.
+And to compute the boolean value \\{j\_prime}, the following
+would suffice: `\ignorespaces$\\{j\_prime}\K\\{true}$; \&{for} $\|n\K1%
+\mathrel{\&{to}}\|k$ \&{do}\unskip\
+\<If $\|p[\|n]$ divides \|j, set $\\{j\_prime}\K\\{false}$\>'.
+
+\fi
+
+\M14. However, it is possible to obtain a much more efficient algorithm by
+using more facts of number theory. In the first place, we can speed
+things up a bit by recognizing that $p_1=2$ and that all subsequent
+primes are odd; therefore we can let \|j run through odd values only.
+Our program now takes the following form:
+
+\Y\P$\4\X14:Increase \|j until it is the next prime number\X\S$\6
+\1\&{repeat} \37$\|j\K\|j+2$;\5
+\X20:Update variables that depend on~\|j\X;\6
+\X22:Give to \\{j\_prime} the meaning: \|j~is a prime number\X;\6
+\4\&{until}\5
+\\{j\_prime}\2\par
+\U section~11.\fi
+
+\M15. The \&{repeat} loop in the previous section introduces a boolean
+variable \\{j\_prime}, so that it will not be necessary to resort to
+a \&{goto} statement. (We are following Dijkstra,$^\Dijk$ not Knuth.$^\goto$)
+
+\Y\P$\4\X4:Variables of the program\X\mathrel{+}\S$\6
+\4\\{j\_prime}: \37\\{boolean};\C{is \|j a prime number?}\par
+\fi
+
+\M16. In order to make the odd-even trick work, we must of course initialize
+the variables \|j, \|k, and $\|p[1]$ as follows.
+
+\Y\P$\4\X16:Initialize the data structures\X\S$\6
+$\|j\K1$;\5
+$\|k\K1$;\5
+$\|p[1]\K2$;\par
+\A section~18.
+\U section~11.\fi
+
+\M17. Now we can apply more number theory in order to obtain further
+economies. If \|j is not prime, its smallest prime factor $p_n$ will
+be $\sqrt j$ or less. Thus if we know a number \\{ord} such that
+$$p[\\{ord}]^2>j,$$ and if \|j is odd, we need only test for divisors
+in the set $\{p[2], \ldots, p[\\{ord}-1]\}$. This is much faster than
+testing divisibility by $\{p[2],\ldots,p[k]\}$, since \\{ord} tends
+to be much smaller than~\|k. \ (Indeed, when \|k is large, the
+celebrated ``prime number theorem'' implies that the value of \\{ord}
+will be approximately $2\sqrt{k/\!\ln k}$.)
+
+Let us therefore introduce \\{ord} into the data structure. A moment's
+thought makes it clear that \\{ord} changes in a simple way when \|j
+increases, and that another variable \\{square} facilitates the
+updating process.
+
+\Y\P$\4\X4:Variables of the program\X\mathrel{+}\S$\6
+\4\\{ord}: \37$2\to\\{ord\_max}$;\C{the smallest index $\G2$ such that
+$p_{ord}^2>j$}\6
+\4\\{square}: \37\\{integer};\C{$\\{square}=p_{ord}^2$}\par
+\fi
+
+\M18. \P$\X16:Initialize the data structures\X\mathrel{+}\S$\6
+$\\{ord}\K2$;\5
+$\\{square}\K9$;\par
+\fi
+
+\M19. The value of \\{ord} will never get larger than a certain value
+\\{ord\_max}, which must be chosen sufficiently large. It turns out that
+\\{ord} never exceeds~30 when $\|m=1000$.
+
+\Y\P$\4\X5:Other constants of the program\X\mathrel{+}\S$\6
+$\\{ord\_max}=30$;\C{$p_{ord\_max}^2$ must exceed $p_m$}\par
+\fi
+
+\M20. When \|j has been increased by~2, we must increase \\{ord} by unity
+when $j=p_{ord}^2$, i.e., when $\|j=\\{square}$.
+
+\Y\P$\4\X20:Update variables that depend on~\|j\X\S$\6
+\&{if} $\|j=\\{square}$ \1\&{then}\6
+\&{begin} \37$\\{ord}\K\\{ord}+1$;\5
+\X21:Update variables that depend on~\\{ord}\X;\6
+\&{end}\2\par
+\U section~14.\fi
+
+\M21. At this point in the program, \\{ord} has just been increased by unity,
+and we want to set $\\{square}:=p_{ord}^2$. A surprisingly subtle point
+arises here: How do we know that $p_{ord}$ has already been computed,
+i.e., that $\\{ord}\L\|k$? If there were a gap in the sequence of prime
+numbers,
+such that $p_{k+1}>p_k^2$ for some~$k$, then this part of the program would
+refer to the yet-uncomputed value $\|p[\|k+1]$ unless some special test were
+made.
+
+Fortunately, there are no such gaps. But no simple proof of this fact is
+known. For example, Euclid's famous demonstration that there are
+infinitely many prime numbers is strong enough to prove only that
+$p_{k+1}<=p_1\ldots p_k+1$. Advanced books on number theory come to our
+rescue by showing that much more is true; for example, ``Bertrand's
+postulate'' states that $p_{k+1}<2p_k$
+for all~$k$.
+
+\Y\P$\4\X21:Update variables that depend on~\\{ord}\X\S$\6
+$\\{square}\K\|p[\\{ord}]\ast\|p[\\{ord}]$;\C{at this point $\\{ord}\L\|k$}\par
+\A section~25.
+\U section~20.\fi
+
+
+\N22. The inner loop.
+Our remaining task is to determine whether or not a given integer~\|j is prime.
+The general outline of this part of the program is quite simple,
+using the value of \\{ord} as described above.
+
+\Y\P$\4\X22:Give to \\{j\_prime} the meaning: \|j~is a prime number\X\S$\6
+$\|n\K2$;\5
+$\\{j\_prime}\K\\{true}$;\6
+\&{while} $(\|n<\\{ord})\W\\{j\_prime}$ \1\&{do}\6
+\&{begin} \37\X26:If $\|p[\|n]$ is a factor of~\|j, set $\\{j\_prime}\K%
+\\{false}$\X;\6
+$\|n\K\|n+1$;\6
+\&{end}\2\par
+\U section~14.\fi
+
+\M23. \P$\X4:Variables of the program\X\mathrel{+}\S$\6
+\4\|n: \37$2\to\\{ord\_max}$;\C{runs from 2 to \\{ord} when testing
+divisibility}\par
+\fi
+
+\M24. Let's suppose that division is very slow or nonexistent on our
+machine. We want to detect nonprime odd numbers, which are odd multiples
+of the set of primes $\{p_2,\ldots,p_{ord}\}$.
+
+Since \\{ord\_max} is small, it is reasonable to maintain an auxiliary table of
+the smallest odd multiples that haven't already been used to show that
+some~\|j is nonprime. In other words, our goal is to ``knock out'' all
+of the odd multiples of each $p_n$ in the set $\{p_2,\ldots,p_{ord}\}$,
+and one way to do this is to introduce an auxiliary table that serves as
+a control structure for a set of knock-out procedures that are being
+simulated in parallel. (The so-called ``sieve of Eratosthenes''
+generates primes by a similar method, but
+it knocks out the multiples of each prime serially.)
+
+The auxiliary table suggested by these considerations is a \\{mult}
+array that satisfies the following invariant condition: For $2\L\|n<\\{ord}$,
+$\\{mult}[\|n]$ is an odd multiple of $p_n$ such that $\\{mult}[n]<j+2p_n$.
+
+\Y\P$\4\X4:Variables of the program\X\mathrel{+}\S$\6
+\4\\{mult}: \37\&{array} $[2\to\\{ord\_max}]$ \1\&{of}\5
+\\{integer};\C{runs through multiples of primes}\2\par
+\fi
+
+\M25. When \\{ord} has been increased, we need to initialize a new element of
+the \\{mult} array. At this point $j=p[\\{ord}-1]^2$, so there is no
+need for an elaborate computation.
+
+\Y\P$\4\X21:Update variables that depend on~\\{ord}\X\mathrel{+}\S$\6
+$\\{mult}[\\{ord}-1]\K\|j$;\par
+\fi
+
+\M26. The remaining task is straightforward, given the data structures
+already prepared. Let us recapitulate the current situation: The
+goal is to test whether or not \|j~is divisible by~$p_n$, without
+actually performing a division. We know that $j$~is odd, and that
+$\\{mult}[\|n]$ is an odd multiple of~$p_n$ such that $\\{mult}[n]<j+2p_n$.
+If $\\{mult}[\|n]<\|j$, we can increase $\\{mult}[\|n]$ by $2p_n$ and the same
+conditions will hold. On the other hand if $\\{mult}[\|n]\G\|j$, the
+conditions imply that \|j~is divisible by~$p_n$ if and only if
+$\|j=\\{mult}[\|n]$.
+
+\Y\P$\4\X26:If $\|p[\|n]$ is a factor of~\|j, set $\\{j\_prime}\K\\{false}$\X%
+\S$\6
+\&{while} $\\{mult}[\|n]<\|j$ \1\&{do}\5
+$\\{mult}[\|n]\K\\{mult}[\|n]+\|p[\|n]+\|p[\|n]$;\2\6
+\&{if} $\\{mult}[\|n]=\|j$ \1\&{then}\5
+$\\{j\_prime}\K\\{false}$\2\par
+\U section~22.\fi
+
+
+\N27. Index.
+Every identifier used in this program is shown here together with a list
+of the section numbers where that identifier appears. The section number
+is underlined if the identifier was defined in that section. However,
+one-letter identifiers are indexed only at their point of definition,
+since such identifiers tend to appear almost everywhere. \[An index like
+this is prepared automatically by the \WEB\ software, and it is appended
+to the final section of the program. However, underlining of section
+numbers is not automatic; the user is supposed to mark identifiers
+at their point of definition in the \WEB\ source file.\]
+
+This index also refers to some of the places where key elements of the
+program are treated. For example, the entries for `Output format' and
+`Page headings' indicate where details of the output format are
+discussed. Several other topics that appear in the documentation
+(e.g., `Bertrand's postulate') have also been indexed. \[Special
+instructions within a \WEB\ source file can be used to insert
+essentially anything into the index.\]
+\fi
+
+
+
+\inx
+\:{Bertrand, Joseph, postulate}, 21.
+\:\\{boolean}, 15.
+\:\|{c}, \[7].
+\:\\{cc}, \[5], 7, 8, 10.
+\:{Dijkstra, Edsger}, 1, 15.
+\:{Eratosthenes, sieve of}, 24.
+\:\\{false}, 13, 26.
+\:\\{integer}, 4, 7, 12, 17, 24.
+\:\|{j}, \[12].
+\:\\{j\_prime}, 13, 14, \[15], 22, 26.
+\:\|{k}, \[12].
+\:{Knuth, Donald E.}, 15.
+\:\|{m}, \[2].
+\:\\{mult}, \[24], 25, 26.
+\:\|{n}, \[23].
+\:\\{new\_line}, \[6], 9, 10.
+\:\\{new\_page}, \[6], 9.
+\:\\{ord}, \[17], 18, 19, 20, 21, 22, 23, 24, 25.
+\:\\{ord\_max}, 17, \[19], 23, 24.
+\:\\{output}, 2, 6.
+\:{output format}, 5, 9.
+\:\|{p}, \[4].
+\:\\{page}, 6.
+\:{page headings}, 9.
+\:\\{page\_number}, \[7], 8, 9.
+\:\\{page\_offset}, \[7], 8, 9.
+\:{prime number, definition of}, 13.
+\:\\{print\_entry}, \[6], 10.
+\:\\{print\_integer}, \[6], 9.
+\:\\{print\_primes}, \[2].
+\:\\{print\_string}, \[6], 9.
+\:\\{row\_offset}, \[7], 9, 10.
+\:\\{rr}, \[5], 8, 9, 10.
+\:\\{square}, \[17], 18, 20, 21.
+\:\\{true}, 4, 13, 22.
+\:\.{WEB}, 1.
+\:\\{write}, 6.
+\:\\{write\_ln}, 6.
+\:\\{ww}, \[5], 6.
+
+\fin
+\:\X11:Fill table \|p with the first \|m prime numbers\X
+\U section~3.
+\:\X22:Give to \\{j\_prime} the meaning: \|j~is a prime number\X
+\U section~14.
+\:\X26:If $\|p[\|n]$ is a factor of~\|j, set $\\{j\_prime}\K\\{false}$\X
+\U section~22.
+\:\X14:Increase \|j until it is the next prime number\X
+\U section~11.
+\:\X16, 18:Initialize the data structures\X
+\U section~11.
+\:\X5, 19:Other constants of the program\X
+\U section~2.
+\:\X10:Output a line of answers\X
+\U section~9.
+\:\X9:Output a page of answers\X
+\U section~8.
+\:\X8:Print table \|p\X
+\U section~3.
+\:\X3:Print the first \|m prime numbers\X
+\U section~2.
+\:\X2:Program to print the first thousand prime numbers\X
+\U section~1.
+\:\X20:Update variables that depend on~\|j\X
+\U section~14.
+\:\X21, 25:Update variables that depend on~\\{ord}\X
+\U section~20.
+\:\X4, 7, 12, 15, 17, 23, 24:Variables of the program\X
+\U section~2.
+\con