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

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.

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}.$$
• That's right. It's exponential time in 10. But 10 is a small constant, and $2^{10}$ is only 1024. Commented Apr 24, 2020 at 21:22