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

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.

share|cite|improve this question
up vote 4 down vote accepted

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


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


share|cite|improve this answer
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

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.