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?

  • $\begingroup$ Probably it will be $\frac{1}{\text{log}(N-\nu({p_i}))}$. Where $\nu({p_i})$ is the number of natural numbers $≤N$ divisible by {$p_i$}, (the primes which doesn't divide $a$). $\endgroup$ – Alapan Das May 23 at 7:03
  • $\begingroup$ Let P be the number of primes less than or equal to N such that P is not 2,3,5,7. Let M be the number of numbers less than or equal to N such that it is not divisible by 2,3,5,7. Are you looking for an estimate for P/N or for an estimate of P/M? $\endgroup$ – Kapil May 23 at 7:14
  • $\begingroup$ Both seem rather trivial - $P$ is just $\ln(N)-\#$primes removed, and $M$ is just $N\prod_p(1-\frac{1}{p})$ $\endgroup$ – obscurans May 23 at 7:42

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)}$$

| cite | improve this answer | |

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.