“

Nearly every example of faulty reasoning that has been published is accompanied by the phrase `of course’ or its equivalent.”

Donald Knuth

“

Nearly every example of faulty reasoning that has been published is accompanied by the phrase `of course’ or its equivalent.”

Donald Knuth

The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct.

Selected Papers on Computer Science(1996)

Donald Knuth

Inspired by a recent discussion on the wonders of , I started thinking about how easy it would be to generate prime numbers in . Well, unsurprisingly, it was presented as an example by Knuth using trial division in *The TeXbook* (download) in 1984:

\documentclass{article} \newif\ifprime \newif\ifunknown % boolean variables \newcount\n \newcount\p \newcount\d \newcount\a % integer variables \def\primes#1{2,~3% assume that #1 is at least 3 \n=#1 \advance\n by-2 % n more to go \p=5 % odd primes starting with p \loop\ifnum\n>0 \printifprime\advance\p by2 \repeat} \def\printp{, % we will invoke \printp if p is prime \ifnum\n=1 and~\fi % ‘and’ precedes the last value \number\p \advance\n by -1 } \def\printifprime{\testprimality \ifprime\printp\fi} \def\testprimality{{\d=3 \global\primetrue \loop\trialdivision \ifunknown\advance\d by2 \repeat}} \def\trialdivision{\a=\p \divide\a by\d \ifnum\a>\d \unknowntrue\else\unknownfalse\fi \multiply\a by\d \ifnum\a=\p \global\primefalse\unknownfalse\fi} \begin{document} % usage The first 100 prime numbers are:~\primes{100} \end{document}

You can also do it by sieving; check out the examples in my GitHub repo.

Beware of bugs in the above code; I have only proved it correct, not tried it.

Donald Knuth(in 1977; explanation here)

Whether you think about it or not, your computer spends much of its time sorting “things”. And there are numerous algorithms for doing this, each with varying measures of complexity and efficiency (for the interested reader, you can discover the wonders of sorting and searching in Volume 3 of Knuth‘s bible: *The Art of Computer Programming*).

Sorting algorithms also provide a gentle introduction to a variety of core computer science concepts, especially data structures and complexity. And what better way to learn some of the common sorting algorithms than through the medium of (Hungarian folk) dance!

For example, quicksort:

Or if you prefer a rather more mundane visualisation of quicksort:

(see more videos at the Algo-Rythmics website)