This is not too slow if you don't re-check uselessly many times the primality of a number. You can first calc a table of the prime numbers <= sqtr(max number you'll have to check the primality of), and then do the maximum of computations that can be done independently of any test case.
If I tell you more, that would tell you the solution to the problem...
BTW, I think this post could have be sent to the V102 forum.
If you're interested in primality testing, I can tell you that actually, many algorithms are probabilistic : they tell you the probablity that the number is prime, but it's not 100% sure. For example, see the problem about Carmichael Numbers (10006), or the Miller Rabin method (see http://www.security-labs.org/index.php3?page=5