Multiples of a set of numbers in a range

Question

Assume there is a set containing integers from 2 to 50, both inclusive, and another containing integers from 500 to 50000, both inclusive.

Question 1. What is the (best) way to find the number/count of items in the second set that are not divisible by any of the elements in the first set?

The straightforward way is to find the sum of all multiples of each element of the first set in the second set and negate the common multiples. Though easily conveyed in words, the working goes something like the following.

All Multiples = (Multiples of 2)
+ (Multiples of 3 - (Sum of Multiples of LCM(3,2)))
+ (Multiples of 5 - (Sum of Multiples of LCM(5,2), LCM(5,3)) + (Sum of Multiples of LCM(5,2,3)))
+ (Multiples of 7 - (Sum of Multiples of LCM(7,2), LCM(7,3), LCM(7,5)) + (Sum of Multiples of LCM(7,2,3), LCM(7,2,5), LCM(7,3,5)) - (Sum of Multiples of LCM(7,5,3,2)))
............
............

And so on. The permutation increases up until the last element and the sign flips for each increment.

Question 2. Can the above formula/method be represented in a standard/simplified way? Are there any topics/tools I need to understand that will help me solve this?

Answer 1

Your formula is the inclusion-exclusion principle. While correct, I think a simple double loop will be much easier to program and faster. Just check each element of the second set against each element of the first and accumulate the results. Note that if you have $n$ elements in the first set, you have $2^n-1$ LCMs to compute and work with.

Answer 2

A lot of the $2^{15}$ counts occuring in the inclusion-exclusion method will be zero. After all, $\operatorname{lcm}(1,2,3,\ldots,50)=3099044504245996706400\gg 50000$. If I were to implement the task as a computer program, I'd simply do someting like

 short A[50001];
 for (int i=0;i<=50000; i++) 
   A[i]=1;
 for (int k=2;k<=50;k++)
   if (A[k])
     for (int i=k; i<=50000; i+=k)
       A[i]=0;
 int count = 0;
 for (int i=500; i<=50000; i++)
   count += A[i];

As already $2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17>50000$, each array entry will be subject to A[i]=0at most six times. Thus we are executing less than only about 300000 statements.