A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself.

A natural number greater than 1 that is not a prime number is called a composite number. For example, 5 is prime because 1 and 5 are its only positive integer factors, whereas 6 is composite because it has the divisors 2 and 3 in addition to 1 and 6. The fundamental theorem of arithmetic establishes the central role of primes in number theory: any integer greater than 1 can be expressed as a product of primes that is unique up to ordering. The uniqueness in this theorem requires excluding 1 as a prime because one can include arbitrarily many instances of 1 in any factorization, e.g., 3, 1 · 3, 1 · 1 · 3, etc. are all valid factorizations of 3.

There are infinitely many primes, as demonstrated by Euclid around 300 BC.  As of January 2016, the largest known prime number has 22,338,618 decimal digits.

There is no known simple formula that separates prime numbers from composite numbers. However, the distribution of primes, that is to say, the statistical behaviour of primes in the large, can be modelled. The first result in that direction is the prime number theorem, proven at the end of the 19th century, which says that the probability that a given, randomly chosen number n is prime is inversely proportional to its number of digits, or to the logarithm of n.

For a long time, number theory in general, and the study of prime numbers in particular, was seen as the canonical example of pure mathematics, with no applications outside of the self-interest of studying the topic with the exception of use of prime numbered gear teeth to distribute wear evenly. In particular, number theorists such as British mathematician G. H. Hardy prided themselves on doing work that had absolutely no military significance.
However, this vision was shattered in the 1970s, when it was publicly announced that prime numbers could be used as the basis for the creation of public key cryptography algorithms. Prime numbers are also used for hash tables and pseudorandom number generators.

Some rotor machines were designed with a different number of pins on each rotor, with the number of pins on any one rotor either prime, or coprime to the number of pins on any other rotor. This helped generate the full cycle of possible rotor positions before repeating any position.

The first 168 prime numbers (all the prime numbers less than 1000) are:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997

There is no known efficient formula for primes.

Ulam’s Spiral

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.

Ulam constructed the spiral by writing down a regular rectangular grid of numbers, starting with 1 at the center, and spiraling out. 

The plot above shows a larger part of the spiral in which the primes are shown as dots.

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.”

A hexagonal prime spiral can also be constructed, as illustrated above (Abbott 2005).

Sokolowski’s Spiral

Aleksander Sokolowski ( 2017) discovered that prime numbers appear on only 4 of 12  lines drawn from the center of a spiral (or set of concentric circles):

 

Blue dots mark the prime numbers (red are exceptions).
Copyright 2017 by A. Sokolowski

There are no prime numbers on lines 2, 3, 4, 6, 8, 9, 10, 12.
Prime numbers are marked as blue dots (exceptions are in magenta).
Copyright 2017 by A. Sokolowski