GolfScript, 14 bytes
~.,{*.!+}*.*\% This outputs this version of Wilson's theorem, used in other answers to this question:
\$(n-1)! \mod{n}\$\$(n-1)!^2 \mod{n}\$
This outputs 1 if it is a prime and 0 if it is not.
~ # Push n ., # Range from 0 to (n-1) {*.!+} # Push block without executing * # Fold .* # Square, it could also be 2?, but for large values of n there would be an error message \% # Mod n What the block does:
* # Multiply .! # Is it 0? + # Add 1 if it was 0 and 0 if it wasn't This uses 3 bytes to avoid the 0, there are ways of removing it from the array using 2:
~.,(;{*}*.*\% The problem here is when the input is 1, in this case after removing the 0 we wouldn't have any number to multiply.