I think Marco's suggestion has merit.

If I faced that problem, I'd use the table Marco suggested and an "array[dword] of bit" and use the primes in the table to set their corresponding bit to 1.

After that, it is a direct access to the array element to determine if a number is prime or not. In addition to that, it would provide a reasonably quick way of determining the prime "floor" and "ceil" of any number that is not a prime.

The bit array would occupy about 1/2gig but you wouldn't need to have it all in memory if you sectioned the array into equal number of primes per range. 1024 ranges would create sections of less than 1 mb each. Each section could be a resource loaded on demand.

Just some thoughts...