Here's a possible intended solution to show that $30031 = 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1$ is composite without factoring it.  Recall the Fermat primality test: if $a^{n-1} \not \equiv 1 \bmod n$, then $n$ cannot be prime.  It turns out that $2^{30030} \equiv 21335 \bmod 30031$, so $30031$ must indeed be composite.  There is a well-known algorithm called <a href="http://en.wikipedia.org/wiki/Exponentiation_by_squaring">binary exponentiation</a> that is reasonably fast to implement by hand and that could conceivably be done on an exam.  (I am not totally convinced that this would be faster than trial division until $p = 59$, though.  And if you followed Leonid's suggestion in the comments your life would be even easier.)