Being limited to 32-bit numbers is only half of the problem.
Using the "Sieve of Eratosthenes" takes far too much memory when you get close to the maximum 32-bit int.
Using the method where you simply check for division with every number up to the square root takes no extra memory but is even slower. This bring me to my next point. This method is far too slow for numbers bigger than 32 bits can handle anyway.
Take a look at http://en.wikipedia.org/wiki/Primality_test
Or better yet, get libmp++-2.0.1d which implements large number types and the Rabin-Miller primality test.