Идея решения задачи:
1. Предподсчитаем кол во простых чисел на преффиксах от [0, 10^6]( это можно сделать предварительно построив решето Эратосфена за O(n*loglogn) )
2. Утверждение : кол - во кратных числу p на преффиксе N равно N/p (где / -  деление с округлением вниз)
3. Тогда чтобы узнать кол во чисел кратных хотя бы одному числу из множества k достаточно воспользоваться формулой *включений-исключений и найти объединение множеств, т е выбирая некоторое подмножество множества K мы собираем составное число из этих простых чисел (для перебора подмножеств воспользуемся перебором всех масок длиной |k| )
* формула включений - исключений :  A(i) - итое множество набора объединение которого нам нужно найти,
(| - объединение, & - пересечение, | | - раземер )
 | |(A) | = SUM_1_n |A(i)| - SUM_i_j (| A(i) & A(j) |) + SUM_i_j_k(| A(i) & A(j) & A(k) |) ..... +
+ (-1) ^ ( n-1 ) SUM_1...n(|A(i)&...A(n)|)
4 Итоговое формула ответа (1 учитываем как не составное число)
ans = n - | |(K) | + |K| - cnt_of_prime[n] - 1(если 1 учтена в решете то вычитать ее не нужно).