I watched a great series once on generating ~prime numbers which explained how to use number theory to check a randomly generated number for a probability of being prime. By using a bunch of weird rules, you can be ~99% sure it's prime without having to do huge computations.