Is there an efficient algorithm for determining the probability a large randomly chosen integer is not divisible by any integer of some set?

Question

Given a set of 10 integers $A = a_1, a_2, \cdots a_{10}$, is there an efficient algorithm which can tell me what's the probability a randomly chosen integer between $1$ and $10^{10}$ is NOT divisible by any member of this set.

I understand the Inclusion-Exclusion principle can be used to solve this problem but I can't figure out how to implement it so that it works efficiently.

Note: When I say "efficient", I mean polynomial time, yet I am not entirely sure what qualifies as polynomial time is this case as both variables are fixed.

Answer 1

Let $\mathbf x$ be a random number in the range $1,\ldots,N$, and let $E_i$ denote the event that $\mathbf x$ is divisible by $a_i$. You are interested in the probability that none of the events $E_1,\ldots,E_m$ happen (in your case, $m = 10$). Using the inclusion-exclusion principle, this reduces to computing the probability of the events of the form $E_{i_1} \land \cdots \land E_{i_k}$, that is, $\mathbf x$ is divisible by all of $a_{i_1},\ldots,a_{i_k}$. Since a $\mathbf x$ is divisible by a bunch of numbers iff it is divisible by their LCM, it suffices to determine the probability that $\mathbf x$ is divisible by $a$.

Among $1,\ldots,N$, the numbers divisible by $a$ are $$ a,2a,3a,\ldots,\lfloor N/a \rfloor a, $$ in total $\lfloor N/a \rfloor$ numbers. Hence the probability that $\mathbf x$ is divisible by $a$ is exactly $$ \frac{\lfloor N/a \rfloor}{N}. $$