[bjornorn]

Checking if a number is a prime or not is much easier than actually factoring it (if it is not a prime).

http://en.wikipedia.org/wiki/Primality_test