7
$\begingroup$


The probability of that a number between 1 to x is prime is $\frac{1}{\ln{x}}$ as per prime number theorem and also the total number of prime numbers between $1$ to $x$ will be $\frac{x}{\ln{x}}$. But if we select $n$ (32 bit) random numbers, what is the probability that $p$ of them are primes?

Or Simply put

What is the probability of picking $p$ primes from $n$ random numbers (32 bit).

TIA..

$\endgroup$
16
$\begingroup$

There are 203,280,221 primes less than $2^{32}$. (Source). So the probability that a random 32-bit number is prime is $203,280,221 / 2^{32} \approx 0.04733$. Assuming you want selection with replacement, i.e. the same number can be picked more than once, the probability of picking $p$ primes from $n$ 32-bit random numbers is, from the probability mass function of the binomial distribution, $$\frac {n!}{p!(n-p)!} 0.04733^p (1-0.04733)^{n-p} . $$

$\endgroup$
  • $\begingroup$ This would be also true for sampling without replacement, provided $n<<2^{32}$. For example if we sampled $n=2^{20}$ numbers without replacement and found them all to be not primes, the probability of a prime on the next draw has only increased to $0.047341$. If they are all primes the probability has decreased to $0.047097$. The probability at each draw must lie between these two limits. $\endgroup$ – probabilityislogic Mar 20 '12 at 15:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.