This site is supported by donations to The OEIS Foundation.

# Formulas for primes

From OeisWiki

There is a longstanding myth that there is no formula for prime numbers.^{[1]} 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^{[2]} to formulas for primes, dividing them into 11 categories:

- A formula for as a function of
*x*. - A formula for as a function of
*n*. - A necessary and sufficient condition for
*n*to be prime. - A function that is prime for each member of its domain.
- A function (the positive part of) whose range consists only of primes, or consists of all of the primes.
- A function whose range contains a high density of primes.
- A formula for the largest prime divisor of
*n*. - A formula for the prime factors of
*n*. - A formula for the smallest prime greater than
*n*. - A formula for in terms of .
- An algorithm for generating the primes.

Similarly, Sato & Straus^{[3]} propose 7 categories for prime-representing functions:

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

Beside Guy, other collections of prime formulas can be found in Ribenboim^{[4]}^{[5]}, Bach & Shallit^{[6]}, and Lopez-Ortiz.^{[7]}

## See also

## References

- ↑ Jeffrey Shallit, No formula for the prime numbers?, January 07 2013 blog entry.
- ↑ Richard Guy, Unsolved Problems in Number Theory, third edition (2004).
- ↑ Cite error: Invalid
`<ref>`

tag; no text was provided for refs named`SatoStraus1970`

- ↑ Paulo Ribenboim, The Little Book of Bigger Primes, second edition. Springer 2004.
- ↑ Paulo Ribenboim, Are there functions that generate prime numbers?,
*College Mathematics Journal***28**:5 (1997), pp. 352–359. - ↑ Eric Bach and Jeffrey Shallit, Algorithmic Number Theory, Volume I: Efficient Algorithms, MIT Press (August 1996).
- ↑ Alex Lopez-Ortiz, ed., Formulae to compute prime numbers (1998). Part of The Sci.Math FAQ Team's Frequently Asked Questions in Mathematics.

## 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]