Finding a prime number between $n$ and $2n$ I am trying to find a prime number between $n$ and $2n$.
I know that the number of primes between $n$ and $2n$ is $n/(2\ln n)$.
I was thinking of choosing a random number between $n$ and $2n$ and check if its prime. If no, repeat.
However, how do I find the repetitions needed to make sure I find a prime with a probability of .99?
Any help would be appreciated.
 A: Your estimate for the number of primes is wrong: there are about
$$\frac{n}{\log n}$$
primes between $n$ and $2n$. More specifically, the number is
$$n/\log n-kn/\log^2n+O(n/\log^3n)$$
where $k=\log4-1=0.386\ldots.$
That aside, you're essentially being asked to use the geometric distribution here. If your chance of failure is
$$
1-\frac{1}{\log n}
$$
then your chance of failure after $k$ trials is
$$
(1-\frac{1}{\log n})^k
$$
and you can solve
$$
(1-\frac{1}{\log n})^k=0.01
$$
by taking logarithms.
As a practical matter you might exclude even numbers from your search. In that case your chance of success per trial doubles and you can solve
$$
(1-\frac{2}{\log n})^k=0.01
$$
instead.
A: Your conjecture is known as the Bertrand postulate:

For every $n > 1$ there is always at least one prime $p$ such that $n < p < 2n$.

Proving the conjecture isn't trivial, you can find a proof by Erdős on Wikipedia. He proved even stronger result that

... for any positive integer $k$, there is a natural number $N$ such that for all $n > N$, there are at least $k$ primes between $n$ and $2n$.

A: By the Prime Number Theorem, ${\pi(2n)}-{\pi(n)} \approx \frac{2n}{\ln(2n)}-\frac{n}{\ln(n)} \approx \frac{n}{2\ln(n)}$. Now that is quite an approximation. But supposing we play by your rules, the probability that we will encounter a prime if we randomly picked a number between $n$ and $2n$ is $\frac{1}{2\ln(n)}$. We say that we run $r$ such trials or repititions such that the probability that there will be at least one prime in the search is $0.99$. Employing binomial distribution we get
$$\begin{align} 1-\left(1-\frac{1}{2\ln(n)} \right)^{r} &= 0.99 \\ 
\left(1-\frac{1}{2\ln(n)} \right)^{r} &= 0.01. \end{align}$$
Solving for $r$ yields
$$ r=\log_{\left(1-\frac{1}{2\ln(n)}\right)}0.01=\frac{\ln(0.01)}{\ln\left(1-\frac{1}{2\ln(n)}\right)}.$$
The number of trials or repititions required such that the probability that we will encounter a prime at least once between $n$ and $2n$ is $\left\lceil \ln(0.01)/\ln\left(1-\frac{1}{2\ln(n)}\right)\right\rceil$.
