[cyborgx7]

Same here. What happened to me is, instead of asking myself "Is this a prime number?" I kept starting to ask myself "Can this number be expressed as a multiplication of two other numbers?" for which the answers are obviously reversed.

[davidamarquis]

Finding divisors is often hard when your number is large. It turns out the condition that a number n can be expressed as a multiple of two other numbers is equivalent to there being a number z less than n except for 1 and n-1 so that (z^2 mod n) == 1.

This condition is the basis of the Miller-Rabin primality test. Sadly its a bit hard for humans to implement this algorithm for mentally proving primality.