Count of numbers till 1000 divisible by atleast one of the first 10 prime numbers?

Question

how can I calculate the count of numbers till 1000 divisible by atleast one of the first 10 prime numbers?

I can calculate count of numbers divisible by either 2 or 3 or 5 but I don't know how to calculate for large set of prime numbers.

Note: I can obviously use the bruteforce way to do this but I'm looking for a generic solution where number range is not limited to 1000. for ex. it could go to 10^18.

Answer 1

I think the most efficient way to calculate this is by brute force. Since $\sqrt{1000}$ is less than the twelfth prime ($37$), any number less than $1000$ not divisible by any of the first ten primes must either be a prime number, or $31^2$ or $1$ (note that $31\cdot37>1000$). Thus the answer is:

$$1000-(\pi(1000)-10)-2=840$$

Where $\pi(n)$ is the number of primes less than or equal to $n$. The above answer can be confirmed by a small computer program. There is no fast way to calculate the exact value of $\pi(n)$, so I don't believe there will be a fast way to calculate the answer to this problem by hand.

EDIT: This is the program I used to verify the answer (Haskell):

primes = [2,3,5,7,11,13,17,19,23,29]
cond n = (0 `elem`) . map (n `mod`) $ primes
answer = length $ filter cond [1..1000]
main = print answer

EDIT 2: Note that this only works because the tenth prime happens to be almost as big as $\sqrt{1000}$. If you were to check how many numbers op to, say, $10^{18}$ are divisible by the first 10 primes, this approach won't work. You can still calculate the answer for $N=2\cdot3\cdot5\cdots29$ within reasonable time by brute force. Letting $f$ be a function giving the desired answer within this range, and $10^{18}=qN+r,0\le r<N$, we can calculate the answer as $qf(N)+f(r)$. Some further optimizations can be made using the inclusion-exclusion principle.

EDIT 3: $f(N)=\phi(N)=(2-1)(3-1)(5-1)\cdots(29-1)$ can be quickly calculated, but $f(r)$ is harder, and will probably require brute force, except in some "lucky" special cases.

Answer 2

By the principle of inclusion-exclusion, the number of integers up to $n$ that are not divisible by any prime in the set $P$ (consisting only of primes) is precisely equal to $$\sum_{S\subseteq P} (-1)^{|S|} \bigg\lfloor \frac{n}{\prod_{p\in S} p} \bigg\rfloor,$$ where $S$ ranges over all subsets of $P$, including the empty set.

When $P$ is the set of the first $10$ primes, this sum only has $1024$ terms, which is vastly better than brute force. When $n=1000$ it would be silly to sum $1024$ terms just to count a few hundred objects. On the other hand, if done intelligently, one could truncate the sum by eliminating terms that are identically zero (because $\prod > n$).