Suppose that there is a prime number. Now I want to approximate the next prime number. (It does not have to be exact.) What would be the time-efficient way to do this?

Edit: what happens if we limit the case to the prime number of the form $4k+1$ where k is a natural number?

Edit: it's fine to replace approximate prime number with finding any prime number that is bigger than the given prime number in a time-efficient way.

  • $\begingroup$ can you explain what you mean by 'approximate the next prime' $\endgroup$ – picakhu Jul 11 '12 at 12:30
  • $\begingroup$ @picakhu edited. $\endgroup$ – Zat Mack Jul 11 '12 at 12:32
  • $\begingroup$ I still cannot make sense of it. Perhaps someone else here understands the question. Is your question 'what is the best(fastest) way to find a prime that is larger than a given prime' One answer is find the largest known prime. That is O(1). $\endgroup$ – picakhu Jul 11 '12 at 12:35
  • $\begingroup$ The next prime after $p$ is certainly less than $2p$ by Bertrand's postulate (which is actually a theorem). $\endgroup$ – lhf Jul 11 '12 at 12:35
  • $\begingroup$ See en.wikipedia.org/wiki/Prime_gap#Upper_bounds $\endgroup$ – lhf Jul 11 '12 at 12:37

You could use the fact that the density of primes around $p$ is about $\frac 1{\ln p}$ to say the next is around $p + \ln p$, but the variance on this estimate is huge. For $4k+1$ primes, the density is about the same as $4k+3$ primes, so the estimate would be $p + 2 \ln p$.

To find the next, just start from $p$ and check all numbers of the form $6k+1$ or $6k+5$ until you find one. You shouldn't have to check toooo many. (On average, $\frac {\ln p}3$)

To find any larger prime, just search the Web for the largest known prime.


well.. an exact calculation could be provided by: $p(n)=(f(n-1)/f(n))*(p(n-1)-1)$ where f(n) is defined as $π(n)$ in this question: Expected smallest prime factor

Well besides that an approximation of the previous formula could be: $ p(n)=(ln(n+1)/ln(n-1))*((ln(n)-ln(n-1))/(ln(n+1)-ln(n))*(p(n-1)-1)$

I will come back with some more infos.

I hope i've helped


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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