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.

18$\begingroup$ You're not pressing the envelope, you're trying to stuff a watermelon into it. I am pretty sure the error in Stirling's formula for $\Gamma(n)$ is way bigger than $n$ for large $n$ no matter how many terms you include, hence your idea has no chance of going anywhere. $\endgroup$ – Harald HancheOlsen Oct 16 '10 at 17:57

5$\begingroup$ @:Harald HancheOlsen:Your point is well taken, but poorly given. The word “envelope” here is not the postal kind, but rather means a specialized case of “boundary” (specifically, sense # 7 of the definition of “envelope” in the MerriamWebster online dictionary). You could have appropriately said, for example, “You are not pressing the envelope, but egregiously elbowing it.” $\endgroup$ – Mike Jones Oct 19 '10 at 0:39
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}(n1)^{n1/2}\exp(n1+1/(12n11))\right\rceil$$ $$\le (n1)!\le$$ $$\left\lfloor\sqrt{2\pi}(n1)^{n1/2}\exp(n1+1/(12n12))\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 highprecision 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. 2629.

2$\begingroup$ The point being that I'm already pretty good at testing primality up to $n = 100$. $\endgroup$ – Theo JohnsonFreyd Oct 17 '10 at 0:24

5$\begingroup$ Yes, but with less than two hours of research, plus a bignum library, you could have a millisecondscale test rather than a nanosecondscale test! $\endgroup$ – Charles Oct 17 '10 at 3:01

2$\begingroup$ Remark: If you use the stronger form of Stirlings's theorem, where the trailing term is a sum over Bernoulli numbers, and you truncate that sum at the optimal point, then you can get much farther but you still lose in the end. The error is computing $n!$ this way is roughly
$n!/(\pi e^{2 \pi n} \sqrt{n})$
, which is greater than $1$ once $n$ is larger than$1455 \approx e^{2 \pi +1}$
. See Concrete Mathematics, Problem 9.26. $\endgroup$ – David E Speyer Oct 21 '10 at 15:02 
1$\begingroup$ @David: I really didn't expect to be able to get that far. With cautious modifications to Wilson's theorem that could probably give primality tests up to ten or fifteen thousand. Ah, wastefulness... $\endgroup$ – Charles Oct 21 '10 at 16:18

1$\begingroup$ The convergent version converges incredibly slowly. We are now swatting flies with glaciers. $\endgroup$ – Fredrik Johansson Oct 4 '12 at 15:39