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.
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, count=2, count=2, count=1, count=1.
Can the principle of inclusion and exclusion be applied in this case or is there any other approach to the problem?