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

   π (x)

   as a function of

   x

   .
2. A formula for

   pn

   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

    pn +1

    in terms of

    p1, p2, ..., pn

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

See also

• Wilson’s theorem

Cite this page as

Charles R Greathouse IV, Formulas for primes.— From the On-Line Encyclopedia of Integer Sequences® Wiki (OEIS® Wiki). [https://oeis.org/wiki/Formulas_for_primes]