Editing Prime number (section)

=== Formulas for primes ===
{{main|Formula 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.<ref name="matiyasevich"/> 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.<ref>{{cite journal | last = Mackinnon | first = Nick | date = June 1987 | doi = 10.2307/3616496 | issue = 456 | pages = 113–114 | journal = [[The Mathematical Gazette]] | title = Prime number formulae | volume = 71| jstor = 3616496 | s2cid = 171537609 }}</ref> 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.<ref name="matiyasevich">{{cite book | last = Matiyasevich | first = Yuri V. | author-link = Yuri Matiyasevich | year=1999 | chapter = Formulas for prime numbers | chapter-url=https://books.google.com/books?id=oLKlk5o6WroC&pg=PA13 | editor1-first=Serge | editor1-last = Tabachnikov | editor-link1=Sergei Tabachnikov| title = Kvant Selecta: Algebra and Analysis | volume = II | publisher = [[American Mathematical Society]] | isbn = 978-0-8218-1915-9 | pages=13–24}}</ref>

Other examples of prime-generating formulas come from [[Mills' theorem]] and a theorem of [[E. M. Wright|Wright]]. These assert that there are real constants <math>A>1</math> and <math>\mu</math> such that
: <math>\left \lfloor A^{3^n}\right \rfloor \text{ and } \left \lfloor 2^{\cdots^{2^{2^\mu}}} \right \rfloor</math>
are prime for any natural number {{tmath|n}} in the first formula, and any number of exponents in the second formula.<ref>{{cite journal |first=E.M. |last= Wright | author-link=E. M. Wright |title=A prime-representing function |journal=[[American Mathematical Monthly]] |volume=58 |issue=9 |year=1951 |pages=616–618 |jstor=2306356 |doi= 10.2307/2306356}}</ref> Here <math>\lfloor {}\cdot{} \rfloor</math> 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 {{tmath|A}} or <math>\mu.</math><ref name="matiyasevich"/>