I'm not sure what your ultimate design objective (and balance) is to be, but you mentioned heavy use of caching, which is probably a very good idea. My thought, however, is that if hard drive space is plentiful, and processor cycles are not, you could cache all primes up to 100,000,000. According to this URL, there are about 5.76 million primes in the range under 100,000,000. If you can store each number in the 0 .. 100,000,000 range as a four-byte (32 bit) word, you'll need 21 Megabytes to cache all primes between 0 and 100,000,000.

Stored as a packed flat file of four-byte words, you could easily perform binary searches on the file, and thus determine primality in O(log N) time, where N is the number of primes you have cached. As for how to come up with this 21MB list, I'm sure there are sites out there that have already generated text-based lists of primes. Just convert that to packed words and presto.

...just thinking. Of course this assumes your design needs allow you all the storage space you want, and that you need the fastest possible solution. And it's not a complete solution, since there may still be times that you need to figure out primes past 100,000,000. For that, you'll still need a quick algorithm for testing primality.