# Approximating next prime number

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.

• can you explain what you mean by 'approximate the next prime' – picakhu Jul 11 '12 at 12:30
• @picakhu edited. – Zat Mack Jul 11 '12 at 12:32
• 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). – picakhu Jul 11 '12 at 12:35
• The next prime after $p$ is certainly less than $2p$ by Bertrand's postulate (which is actually a theorem). – lhf Jul 11 '12 at 12:35
• – 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)$