In fact, Fermat's Little Theorem can be strengthened; for example, Euler showed that if p is prime, then a^{(p-1)/2} must be 1 or -1 and explained how to compute it.  This gives a stronger test for primality, and the notion of an Euler pseudoprime to base a.  A further strengthening of Fermat's Little Theorem gives the notion of a strong pseudoprime to base a, which you might like to look up and to program.  Only one number less than 10^8 is a strong pseudoprime to each of the bases 2, 3 and 5 - can you find it?

If a number n is not prime, this is usually very quickly demonstrated with one of these tests.  However, if a number passes these tests, while it is very likely to be prime, further testing is necessary to prove it definitively.