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?
4
$\begingroup$
number-theory
algorithms
prime-numbers
-
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