I've been studying some number theory, and I came across this problem:
Lagrange’s prime number theorem states that as N increases, the number of primes less than $N$ is $Θ(N/ log(N))$.
Consider the following algorithm to choose a random n-bit prime:
1) Pick a random n-bit number $k$.
2) Run a primality test on $k.$
3) If it passes the test, output $k$; else repeat the process.
Show that this algorithm will sample on average $O(n)$ random numbers before hitting a prime.
I'm guessing I need to approach this probabilistically. Let $p$ be the probability that we randomly choose a prime. Let $E$ be the expected number of random numbers to choose before hitting a prime. Then, I need to express $E$ in terms of $p$, and show that it is less than or equal to $n$, right? Since, if we sample on average $O(n)$ numbers, then the expectation $E$ should be $\le n$.
But I'm a bit stuck on how to go about doing this. Is each event of choosing a random number binomial? Either we choose a prime or we don't, and each event is independent. But the expectation of a binomial RV is $np$, which is clearly not $\le n$.
I feel like I'm going about this all wrong. What am I missing here? Am I even on the right track? Thanks for your help.