Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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.

share|cite|improve this question
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
See – lhf Jul 11 '12 at 12:37
up vote 4 down vote accepted

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.

share|cite|improve this answer

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

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.