4
$\begingroup$

What is the most efficient algorithm for finding prime numbers which belongs to the interval $(p,p^2)$ , where $p$ is some arbitrary prime number? I have heard for Sieve of Atkin but is there some better way for such specific case which I described?

  • 0
    Every positive natural number can be written as the sum of distinct powers of 2, so I don't see how your statement is useful.2011-09-19

1 Answers 1

2

This is essentially the same as asking for the primes below x for arbitrary x.

There are essentially only two practical sieves for the task: Eratosthenes and Atkin-Bernstein. Practically, the sieve of Eratosthenes is fastest; the Atkin-Bernstein sieve might overtake it eventually but I do not know of any implementations that are efficient for large numbers.

Unless your range is very small, it will not fit in memory. In that case it is critical to use a segmented sieve; both Eratosthenes and Atkin-Bernstein do this naturally.

If you're looking for an existing program, try yafu, primesieve, or primegen. The first two are modified sieves of Eratosthenes and the last is an Atkin-Bernstein implementation, though efficient only to $2^{32}$ (or p = 65521 in your case).