This site is supported by donations to The OEIS Foundation.

# Formulas for primes

There is a longstanding myth that there is no formula for prime numbers. In fact, there are hundreds of formulas for primes of many different types. Guy devotes an entire section, A17 (with over a hundred references!), of his book to formulas for primes, dividing them into 11 categories:

1. A formula for $\pi (x)$ as a function of x.
2. A formula for $p_{n}$ as a function of n.
3. A necessary and sufficient condition for n to be prime.
4. A function that is prime for each member of its domain.
5. A function (the positive part of) whose range consists only of primes, or consists of all of the primes.
6. A function whose range contains a high density of primes.
7. A formula for the largest prime divisor of n.
8. A formula for the prime factors of n.
9. A formula for the smallest prime greater than n.
10. A formula for $p_{n+1}$ in terms of $p_{1},p_{2},\ldots ,p_{n}$ .
11. An algorithm for generating the primes.

Similarly, Sato & Straus propose 7 categories for prime-representing functions:

1. Constant functions
2. Functions which are essentially equivalent to the definition of primes
3. Reinterpretation of (Eratosthenes) sieve method
4. Adding 1 p-times where p is prime
5. Functions which are constructed assuming prime sequence from the beginning
6. Analytic functions constructed by interpolation procedures
7. Use of Wilson's theorem or similar formulas which characterize prime numbers

Beside Guy, other collections of prime formulas can be found in Ribenboim, Bach & Shallit, and Lopez-Ortiz.