If you're interested in prime numbers, you should consider implementing a probabilistic primality test.
What does it mean? If a number fails this test, it is not a prime. If the number passes, it may be a prime.

Instead of providing a bunch of information, I suggest starting from this page, describing Rabin-Miller test.

I also invite you to visit my links page: it may be useful (well, someone said me it was :))

Larsen