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.

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. 

