Pressing the envelope, presumably the best scenario would be a simple proof of the Prime Number Theorem. After all, Wilson’s Theorem gives a necessary and sufficient condition, in terms of the Gamma Function, for a number to be a prime, and Stirling’s Formula specifies the asymptotic behaviour of the Gamma Function.



Has Stirling’s Formula ever been applied, with interesting consequence, to Wilson’s Theorem?
Using Robbins' [1] form of Stirling's formula,


$$\sqrt{2\pi}n^{n+1/2}\exp(-n+1/(12n+1))< n!< \sqrt{2\pi}n^{n+1/2}\exp(-n+1/(12n))$$


we get


$$\left\lceil\sqrt{2\pi}(n-1)^{n-1/2}\exp(-n-1+1/(12n-11))\right\rceil$$
$$\le (n-1)!\le$$
$$\left\lfloor\sqrt{2\pi}(n-1)^{n-1/2}\exp(-n-1+1/(12n-12))\right\rfloor$$


which is accurate enough to distinguish prime from composite for $n\le8$. For larger numbers, the error bound is too large.




---


This can be extended further using a modification of Wilson's theorem: for n > 9,
$$\lfloor n/2\rfloor!\equiv0\pmod n$$
if and only if n is composite. This allows testing 10 through 15, plus (with some cleverness) 17.


With tighter explicit bounds and high-precision evaluation, it might be possible to test as high as 100 with related methods: direct evaluation up to 25 and the 'divide by 4' variant of the above for n > 25.


This is not so much 'using a cannon to swat a fly' (using methods more powerful than needed) as it is 'using the space station to swat a fly': the methods must be extremely powerful and accurate to do very little.




---


[1] H. Robbins, "A Remark on Stirling's Formula." *The American Mathematical Monthly* **62** (1955), pp. 26-29.


