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... –  pedja Sep 16 '11 at 10:54
@GerryMyerson,all primes... –  pedja 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).