# Prime Numbers in PostScript

### Hello, primes!

Over the years, I’ve had to learn quite a few programming languages (those tend to come and go). There’s a tradition, going back at least to `C`

, to start with a so-called *hello, world* program. Eventually, I grew tired of saying *hello* to a world that never said *hello* back, and made my first foray into any new language a program that computes a list of prime numbers. Conceptually, it’s a little more interesting than *hello, world* because it requires conditionals, arithmetic and a form of iteration (or recursion).

I won’t bore the reader with examples from mainstream languages. The focus of this page is programming primes numbers in *PostScript*, a language that was designed for graphics. Still, I have to mention one of my favorite prime numbers program, written for the `dc`

unix command (arguably, not a programming language):

```
2p3p[dl!d2+s!%0=@l!l^!<#]s#[s/0ds^]s@[p]s&[ddvs^3s!l#x0<&2+l.x]ds.x
```

Feed this line to `dc`

and it will start spewing prime numbers. Using `!`

, `@`

and `#`

as variable names makes the program adequately unreadable and I used it for a long time as my email signature line. I had to stop because it confused readers too much (I’m referring to human beings, not email software).

### Programming in PostScript

Before `pdf`

, there was PostScript, developed by the same people, Adobe. In contrast to `pdf`

, however, PostScript is a full-fledged programming language. Because it is stack-based (like dc), it allows for recursion, and of course, it has all the arithmetic needed for graphics. So, one can write a PostScript program to compute prime numbers. Here is one that calculates all primes between 2 and 9973. Just a plain table of prime numbers. The fun part is that it is the *printer* that computes it.

### Ulam’s spiral

PostScript being a language for *graphics*, it can be used for more than just a table of numbers. In the world of completely useless stuff, there is something called *Ulam’s spiral*. It’s obtained from writing positive integers in a (squarish) spiral and crossing out all the non-primes:

```
x -x-99-98-97-96-95-94-93-92-91 @-----------@-----------------|
| | | |
x 65-64-63-62-61-60-59-58-57 90 | |-----------@-----@-----| |
| | | | | | | |
x 66 37-36-35-34-33-32-31 56 89 @ | @-----------------@ | @
| | | | | | | | | | | |
x 67 38 17-16-15-14-13 30 55 88 | @ | @-----------@ | | |
| | | | | | | | | | | | | | | |
x 68 39 18 5--4--3 12 29 54 87 | | | | @-----@ | @ | |
| | | | | | | | | | | | | | | | | | | |
x 69 40 19 6 1--2 11 28 53 86 | | | @ | --@ @ | @ |
| | | | | | | | | | | | | | | | | |
x 70 41 20 7--8--9-10 27 52 85 @ | @ | @--------| | | |
| | | | | | | | | | | | | |
x 71 42 21-22-23-24-25-26 51 84 | @ | |-----@--------| | |
| | | | | | | | | |
x 72 43-44-45-46-47-48-49-50 83 @ | @-----------@--------| @
| | | | | |
x 73-74-75-76-77-78-79-80-81-82 | @-----------------@--------|
| |
x--x--x--x--x--x--x--x--x--x--x... |-----@------------------------...
```

What (some) people find interesting is that, on a large enough spiral, patterns seem to start emerging. This is a snapshot taken from a larger spiral, where one can see diagonal lines (sort of):

This picture was generated from rendering a PostScript program (here). The program actually draws round discs for the prime numbers and has the option of drawing the spiral and printing the numbers inside the discs as well. If you use a PostScript renderer to zoom in a large spiral, you can see this:

Note that each number must be tested for primality, using a naive and inefficient algorithm. This makes the rendering of a spiral somewhat computationally expensive. It’s not too bad when using a renderer like `ghostscript`

on a desktop computer, but when the printer has to do all the work… It gets even worse with some printers that translate PostScript into something else (like PCL) and don’t necessarily expect that the file they’re printing is actually computing prime numbers!

#### Links:

- PostScript source code for the table of prime numbers
- PostScript source code for Ulam’s spiral
- MathWorld page on Ulam’s spiral
- Wikipedia page on Ulam’s spiral
- more on Ulam’s spiral
- Adobe page on PostScript
- another experiment in PostScript programming: L-systems