Check Slashdot today for a link to a paper with the current best known primality testing algorithm in terms of theoretical speed without relying on randomness! You can also look for the Miller-Rabin algorithm on the web.

I see the algorithm, but how on earth do I put that into a form of C++ ???

For everyone else, you can find this algorithm here, on page 4:

http://www.cse.iitk.ac.in/primality.pdf


How could this be turned into C++ code?

I didn't really peruse that one myself, but Miller-Rabin is pretty straightforward if you have routines for fast modular arithmetic on "bignum"'s available.