# How to find primes between $p$ and $p^2$ where $p$ is arbitrary prime number?

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?

• I think you mean "arbitrary" prime number. Otherwise you should specify a distribution over the primes. – joriki Sep 16 '11 at 10:45
• 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. – Yuval Filmus Sep 16 '11 at 10:47
• @joriki,Yes that is better word... – Peđa Terzić Sep 16 '11 at 10:54
• @GerryMyerson,all primes... – Peđa Terzić Sep 16 '11 at 11:57
• That's probably no easier than simply finding all primes below $p^2$. – Henning Makholm Sep 16 '11 at 12:10

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