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?
How to find primes between $p$ and $p^2$ where $p$ is arbitrary prime number?
-
3I think you mean "arbitrary" prime number. Otherwise you should specify a distribution over the primes. – 2011-09-16
-
1Since 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. – 2011-09-16
-
0@joriki,Yes that is better word... – 2011-09-16
-
0Do you want to find *all* the primes between $p$ and $p^2$? or just one or two? or do you just want to know how many there are? – 2011-09-16
-
1@GerryMyerson,all primes... – 2011-09-16
-
3That's probably no easier than simply finding all primes below $p^2$. – 2011-09-16
-
0I doubt you'll find an algorithm that requires $p$ to be prime. Is there reason to suspect that the set of primes between $n$ and $n^2$ has some nice property when $n$ is prime that isn't true when $n$ is not prime? – 2011-09-16
-
0@ThomasAndrews,Each prime number that is greater than $p$ and less than $p^2$ can be represented as sum of prime powers with bases less or equal to $p$ so that is reason of such boundaries... – 2011-09-16
-
0@pedja, that's a very incomplete statement. How many prime powers? I don't see that as remotely useful for actually finding such primes, given $p$. – 2011-09-17
-
0@ThomasAndrews,number of prime powers =( number of primes less or equal to p )- 1,where exponents are nonnegative integers and coefficients are equal to 1.Such sum can produce any prime number greater than $p$ and less than $p^2$. – 2011-09-17
-
0Every 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
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).