Determining number of elements divisible by at least one prime of set I have an array ($|A|\leq 10^6$) of numbers ($A_i\leq10^6$) and a set of prime numbers. I have to find the count of the elements in the array that are divisible by at least one of the numbers in the given set.

For example:


  Array: {3,5,7,15,21,143}
  
  Set: {3,5,7}
  
  Output : 5 


The numbers are 3(3), 5(5), 7(7), 15(3,5), 21(3,7).

If the array size is $10^6$, an $n^2$ algorithm would time out.

Possible approach: I can preprocess all numbers in the array and store the count of elements each prime factors appear in. 

For the example given above : The prime factors are 3,5,7,11,13 and values of the count array will be count[3]=3, count[5]=2, count[7]=2, count[11]=1, count[13]=1.

Can the principle of inclusion and exclusion be applied in this case or is there any other approach to the problem?
One possible approach is to use the GCD algorithm: calculate the GCD of each number in your array with the product of the given primes.