4
$\begingroup$

If I shoot in the dark and pick a random number that's $, 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.

1 Answers 1

4

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)}\;.$

  • 1
    @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](http://en.wikipedia.org/wiki/Expected_value), which is a probabilistic generalization of an average.2011-10-28