Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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