0

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.

Andy
  • 155
  • 1
  • 13
  • How large these numbers are? The basic method to check primality is [trial division](http://en.wikipedia.org/wiki/Trial_division), that is rather sufficient for small numbers on relatively fast machines. It can be optimized by a) odd divisors b) only prime divisors. See [this answer](http://stackoverflow.com/a/27337333/586873) for an illustration. – Grzegorz Szpetkowski Dec 13 '14 at 09:26

1 Answers1

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).

chiastic-security
  • 20,430
  • 4
  • 39
  • 67