Take the 2-minute tour ×
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.

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|improve this question

1 Answer 1

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

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

share|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
5  
@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
1  
Apologies to all for that $1/\log n$. Henning, thanks. –  Gerry Myerson Oct 27 '11 at 23:51
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, which is a probabilistic generalization of an average. –  joriki Oct 28 '11 at 0:12

Your Answer

 
discard

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.