# What is the probability of picking a random prime < n?

If I shoot in the dark and pick a random number that's $<n$, what's the probability that the number will be prime? How many guesses, on average, would it take to get a prime number?

I would really like to understand the reasoning behind the answer, and not just a one-line formula.

-

Assuming that by picking a random number less than $n$ you mean randomly picking a natural number less than $n$ with uniform distribution over all such numbers, the answer is

$$\frac{\pi(n-1)}{n-1}\;,$$

where $\pi$ is the prime-counting function, since $\pi(n-1)$ of the $n-1$ numbers you're choosing from are prime. That article has a lot of information on that function, which it wouldn't make sense to reproduce here; feel free to ask if there's more you want to know that you can't find there.

The average number of trials until the first success given a probability $p$ of success is $1/p$, so the average number of trials in this case would be

$$\frac{n-1}{\pi(n-1)}\;.$$

-
And for large $n$ that average number of trials is asymptotic to $1/\log n$. – Gerry Myerson Oct 27 '11 at 23:30
@Gerry, number of trials is (asymptotic to) $\log n$ -- it cannot be less than 1. The reciprocal is the probability in each trial. – Henning Makholm Oct 27 '11 at 23:33
Thanks. Assuming we use Gerry's approximation, would the average number of trials be log n or (log n)/2 ? – Mark R Oct 27 '11 at 23:40
Apologies to all for that $1/\log n$. Henning, thanks. – Gerry Myerson Oct 27 '11 at 23:51
@Mark: No, the averaging has already been done. Dividing by $2$ only applies if you average two quantities. If you average $n$ quantities, you have to divide by $n$, and in the present case, the "average" should more properly be called the expected value, which is a probabilistic generalization of an average. – joriki Oct 28 '11 at 0:12