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?

$\endgroup$
  • 3
    $\begingroup$ I think you mean "arbitrary" prime number. Otherwise you should specify a distribution over the primes. $\endgroup$ – joriki Sep 16 '11 at 10:45
  • 1
    $\begingroup$ Since the primes become (somewhat) sparser as you go, you're probably going to focus on a small interval $[p,p+O(\log p)]$ anyway. So I'm not sure that having such a big range at your disposal is of any help. $\endgroup$ – Yuval Filmus Sep 16 '11 at 10:47
  • $\begingroup$ @joriki,Yes that is better word... $\endgroup$ – Peđa Terzić Sep 16 '11 at 10:54
  • 1
    $\begingroup$ @GerryMyerson,all primes... $\endgroup$ – Peđa Terzić Sep 16 '11 at 11:57
  • 3
    $\begingroup$ That's probably no easier than simply finding all primes below $p^2$. $\endgroup$ – Henning Makholm Sep 16 '11 at 12:10
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.