section_path: Elementary properties/Formulas for primes
section_name: Formulas for primes
paragraph_text: Formulas for primes
  
  There is no known efficient formula for primes. For example, there is no non-constant polynomial, even in several variables, that takes only prime values. However, there are numerous expressions that do encode all primes, or only primes. One possible formula is based on Wilson's theorem and generates the number 2 many times and all other primes exactly once. There is also a set of Diophantine equations in nine variables and one parameter with the following property: the parameter is prime if and only if the resulting system of equations has a solution over the natural numbers. This can be used to obtain a single formula with the property that all its positive values are prime.
  
  Other examples of prime-generating formulas come from Mills' theorem and a theorem of Wright. These assert that there are real constants A > 1 {\displaystyle A>1} and μ {\displaystyle \mu } such that
  
  are prime for any natural number n {\displaystyle n} in the first formula, and any number of exponents in the second formula. Here ⌊ ⋅ ⌋ {\displaystyle \lfloor {}\cdot {}\rfloor } represents the floor function, the largest integer less than or equal to the number in question. However, these are not useful for generating primes, as the primes must be generated first in order to compute the values of A {\displaystyle A} or μ. {\displaystyle \mu.}