Editing Formula for primes (section)

==Formulas based on Wilson's theorem==

A simple formula is
:<math>f(n) = \left\lfloor \frac{n! \bmod (n+1)}{n} \right\rfloor (n-1) + 2</math>
for positive [[integer]] <math>n</math>, where <math>\lfloor\ \rfloor</math> is the [[floor function]], which rounds down to the nearest integer.
By [[Wilson's theorem]], <math>n+1</math> is prime if and only if <math>n! \equiv n \!\!\!\pmod{n+1}</math>. Thus, when <math>n+1</math> is prime, the first factor in the product becomes one, and the formula produces the prime number <math>n+1</math>. But when <math>n+1</math> is not prime, the first factor becomes zero and the formula produces the prime number 2.<ref>{{citation
 | 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>
This formula is not an efficient way to generate prime numbers because evaluating <math>n! \bmod (n+1)</math> requires about <math>n-1</math> multiplications and reductions modulo <math>n+1</math>.

In 1964, Willans gave the formula
:<math>p_n = 1 + \sum_{i=1}^{2^n} \left\lfloor \left(\frac{n}{\sum_{j=1}^i \left\lfloor\left(\cos \frac{(j-1)! + 1}{j} \pi\right)^2\right\rfloor }\right)^{1/n} \right\rfloor</math>
for the <math>n</math>th prime number <math>p_n</math>.<ref>{{citation
 | last = Willans | first = C. P.
 | date = December 1964
 | doi = 10.2307/3611701
 | issue = 366
 | pages = 413–415
 | journal = [[The Mathematical Gazette]]
 | title = On formulae for the <math>n</math>th prime number
 | volume = 48
 | jstor = 3611701
 | s2cid = 126149459
 }}.</ref>
This formula reduces to<ref>{{citation
 | last1 = Neill | first1 = T. B. M.
 | last2 = Singer | first2 = M.
 | date = October 1965
 | doi = 10.2307/3612863
 | issue = 369
 | jstor = 3612863
 | journal = [[The Mathematical Gazette]]
 | pages = 303–303
 | title = To the Editor, ''The Mathematical Gazette''
 | volume = 49}}</ref><ref>{{citation
 | last1 = Goodstein | first1 = R. L.
 | last2 = Wormell | first2 = C. P.
 | date = February 1967
 | doi = 10.2307/3613607
 | issue = 375
 | journal = [[The Mathematical Gazette]]
 | jstor = 3613607
 | pages = 35–38
 | title = Formulae For Primes
 | volume = 51}}</ref>
:<math>p_n = 1 + \sum_{i=1}^{2^n}[\pi(i) < n];</math> 
that is, it tautologically defines <math>p_n</math> as the smallest integer <math>m</math> for which the [[prime-counting function]] <math>\pi(m)</math> is at least <math>n</math>. This formula is also not efficient. In addition to the appearance of <math>(j-1)!</math>, it computes <math>p_n</math> by adding up <math>p_n</math> copies of <math>1</math>; for example,
:<math>p_5 = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 0 + 0 + \dots + 0 = 11.</math>

The articles ''What is an Answer?'' by [[Herbert Wilf]] (1982)<ref>{{citation
 | last = Wilf | first = Herbert S. | author-link = Herbert Wilf
 | doi = 10.2307/2321713
 | issue = 5
 | journal = [[The American Mathematical Monthly]]
 | jstor = 2321713
 | mr = 653502
 | pages = 289–292
 | title = What is an answer?
 | volume = 89
 | year = 1982}}</ref> and ''Formulas for Primes'' by [[Underwood Dudley]] (1983)<ref>{{citation
 | last = Dudley | first = Underwood | author-link = Underwood Dudley
 | doi = 10.2307/2690261
 | issue = 1
 | journal = [[Mathematics Magazine]]
 | jstor = 2690261
 | mr = 692169
 | pages = 17–22
 | title = Formulas for primes
 | volume = 56
 | year = 1983}}</ref> have further discussion about the worthlessness of such formulas.