A question about the probability of being a prime?

85 Views Asked by At

If we chose a random number $a \leq N$, then, the probability for $a$ to be a prime is $\frac{1}{\log N}$.

Now, if there are some primes that do not divide $a$, then what is the probability for $a$ to be a prime?

EX: if $a \leq 100000$, and both of {2,3,5,7} don't divide $a$, then what is the probability for $a$ to be a prime?

1

There are 1 best solutions below

0
On

First off, the result that the density of the primes is $\frac{1}{\ln N}$ is asymptotic, as in it holds as a limit (so asking specifically $a\leq10^5$ means you get an approximation to the true answer).

Next, simply notice that for sufficiently large $N$, we have that $\frac{1}{2}$ of numbers are not divisible by $2$, $\frac{2}{3}$ are not divisible by $3$, etc. These are all independent for sufficiently large $N$.

So, the count of numbers below $N$ that are not divisible by $P=\{2,3,5,7\}$ is just $$N\prod_{p\in P}\left(1-\frac{1}{p}\right)\text{.}$$

The numerator, the number of primes that are not in $P$, is even easier: there are $\Omega(N/\ln(N))$ total primes, minus all $\left|P\right|=4$ forbidden ones.

The answer is $$\frac{\frac{N}{\ln(N)}-\left|P\right|}{N\prod_{p\in P}\left(1-\frac{1}{p}\right)}$$