Jemediah, Techgnome, et al. OP said he only needed primes up to 10^10 in size. Why not use Logophobic's prime number generator (or mine which is a bit slower) to first generate and store all of these primes in a file. Then search the appropriate file to see if a match exists.

If it does not, then that solves the problem. Seem reasonable?