1
$\begingroup$

I'm writing a program that finds the nth prime number, so if n was 10, the answer would be 29. I need to find an upper bound to search through though so if n was 10, the upper bound would be 30 (or any number before the next prime number which is 31).

Any ideas?

$\endgroup$
3

1 Answer 1

Reset to default
0
$\begingroup$

The number of primes below a given number, $\pi(x)$ can be estimated by:

$\pi(x) \approx \frac{x}{\ln(x)}$.

If you can find a "good" way to invert that function (and add maybe 20% uncertainty in there for small numbers), you can find the estimated upper bound.

$\endgroup$
2
  • 1
    $\begingroup$ The $r = \pi \ln \pi$ and $s = \pi (\ln \pi + \ln \ln \pi)$ are first and second-order approximations for retrieving $x$ from costrom's formula. For $\pi = 10$, these yield $r=23$ and $s=31$. $\endgroup$
    – user3294068
    Commented Oct 12, 2015 at 18:20
  • $\begingroup$ Only an aproximation : prime (n)=n*(ln (n)+ln (ln (n))-0.955) whit error small 4000 if n <10^7.It is a shapr approximation $\endgroup$
    – florin
    Commented Aug 1, 2016 at 3:37

Not the answer you're looking for? Browse other questions tagged .