The prime spiral, also known as Ulam's spiral, is a plot in which the positive integers are arranged in a spiral (left figure), with primes indicated in some way along the spiral. In the right plot above, primes are indicated in red and composites are indicated in yellow.
The plot above shows a larger part of the spiral in which the primes are shown as dots.
Unexpected patterns of diagonal lines are apparent in such a plot, as illustrated in the above 
grid. This construction was first made by Polish-American mathematician Stanislaw
Ulam (1909-1986) in 1963 while doodling during a boring talk at a scientific meeting.
While drawing a grid of lines, he decided to number the intersections according to
a spiral pattern, and then began circling the numbers in the spiral that were primes.
Surprisingly, the circled primes appeared to fall along a number of diagonal straight
lines or, in Ulam's slightly more formal prose, it "appears to exhibit a strongly
nonrandom appearance" (Stein et al. 1964). The spiral appeared on the
March 1964 cover of Scientific American magazine.
Remarkably, noted science fiction author Arthur C. Clarke described the prime spiral in his novel The City and the Stars (1956, Ch. 6, p. 54). Clarke wrote, "Jeserac sat motionless within a whirlpool of numbers. The first thousand primes.... Jeserac was no mathematician, though sometimes he liked to believe he was. All he could do was to search among the infinite array of primes for special relationships and rules which more talented men might incorporate in general laws. He could find how numbers behaved, but he could not explain why. It was his pleasure to hack his way through the arithmetical jungle, and sometimes he discovered wonders that more skillful explorers had missed. He set up the matrix of all possible integers, and started his computer stringing the primes across its surface as beads might be arranged at the intersections of a mesh."
However, Clarke never actually performed this thought experiment (pers. comm. to E. Pegg Jr., May 27, 2002), thus leaving discovery of the unexpected properties of the prime spiral to Ulam seven years later.
M. Charpentier has written a PostScript file which can be downloaded to a printer and draws a prime spiral.
A hexagonal prime spiral can also be constructed, as illustrated above (Abbott 2005).
