Divisibility via Inclusion-Exclusion

Question

Let $N$ be a large natural number, let $A$ be a subset of naturals, and ask:

How many numbers $n\leq N$ are divisible by one or more numbers in $A$.

This is a classical application of the Inclusion-Exclusion principle. Indeed, if for each $i$ we set $A_i$ to be those numbers $n\leq N$ divisible by $i$, then $A_{i_1} \cap\cdots\cap A_{i_k} = A_k$ where $k$ is the lcm of the $i_j$ and so it's easy to evaluate $$ \Big| \bigcup_{i\in A} A_i\Big| = \sum_{\emptyset\not=B\subset A} (-1)^{1+|B|} \Big| \bigcap_{i\in B} A_i\Big| $$ However, this will take around $2^{|A|}$ time and so if $A$ is large, it becomes intractable.

There is something odd in my mind though: what if $A$ is all numbers between 2 and 100? Well, then we don't need to check divisibility by 4, as checking for 2 is enough. Continuing, we see that actually we can replace $A$ be the set of primes less than 100, and I strongly suspect we can't do better (as we end up simulating a sieving method, basically). But what if $A$ is the numbers between 51 and 100? Then there seems no naive reduction, and this becomes worse than testing for the bigger set of all numbers between 2 and 100.

Is there a more sophisticated method? Especially when $A=[51,100]$ or similar examples.

Answer 1

You used a shortcut to only use primes, but you may may be able to forget inclusion-exclusion and just sieve with your values example.

Using R to find the number in the first million integers divisible by integers in $[51,100]$ needs fewer than $50\times 10^6$ trial divisions:

sieve <- function(n,x){
  remaining <- n
  for (y in x){
    remaining  <- remaining[remaining  %% y != 0]
    }
  return(remaining)
  }

lengthnotsieved <- function(n,x){
  return(length(n) - length(sieve(n,x)))
  }

lengthnotsieved(1:10^6, 51:100) 
# 401115

is very fast.