If I shoot in the dark and pick a random number that's $ I would really like to understand the reasoning behind the answer, and not just a one-line formula.
What is the probability of picking a random prime < n?
4
$\begingroup$
probability
prime-numbers
1 Answers
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)}\;.$$
-
0And for large $n$ that average number of trials is asymptotic to $1/\log n$. – 2011-10-27
-
5@Gerry, number of trials is (asymptotic to) $\log n$ -- it cannot be less than 1. The reciprocal is the probability in each trial. – 2011-10-27
-
0Thanks. Assuming we use Gerry's approximation, would the average number of trials be log n or (log n)/2 ? – 2011-10-27
-
0@Mark: As Henning wrote, it's asymptotic to $\log n$. Why do you think it might be $(\log n)/2$? – 2011-10-27
-
1Apologies to all for that $1/\log n$. Henning, thanks. – 2011-10-27
-
0@joriki I'm probably getting confused by the word "average" that it should be divided by 2 – 2011-10-28
-
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