Check if a number is prime without sieve

Question

So i need to solve a problem that finds the n-th number that verifies the following: it is the sum of two consecutive primes and it gives an integer square root. My problem is that the sieve of eratosthenes uses too much memory and the naive checking for a prime is too slow. Any way to solve this fast and without aditional memory? I tried using fermat's theorem but it turned out to be slower.

Thanks in advance.

Answer 1

You could use Rabin-Miller for the primality testing. It's probabilistic, so it tells you only that a number is probably prime, but you can set the level of certainty. It's extremely quick, and low on memory requirements.

Obviously you need only consider squares of even numbers, since only an even number can be the sum of two primes (once you've got past 2).