I've been working on this problem for quite some time and believe I'm stuck. Would be glad to hear any insights on it.
I need an efficient way to determine how many numbers less than $N$ are not divisible by any prime $p_1, p_2, \ldots, p_n$ from a given set. Using the inclusion-exclusion principle, one can calculate it as follows:
$$ \sum_{1 \le i \le n}\Biggl\lfloor\frac{N}{p_i}\Biggl\rfloor - \sum_{1 \le i < j \le n}\Biggl\lfloor\frac{N}{p_ip_j}\Biggl\rfloor + \sum_{1 \le i < j < k \le n}\Biggl\lfloor\frac{N}{p_ip_jp_k}\Biggl\rfloor - \ldots $$
I've got an iterative procedure that exhausts all possible combinations of $p_i$ such that their product is less than $N$, and it works fast enough for a single calculation, but I need to perform around $10$ million such calculations with $N$ around $10^{12}\ldots10^{14}$ and $p_i$ being small primes (less than $100$), around $15$ of them.
The procedure starts with $\{p_1\}$ and sorted list of primes. If combination product is less than $N$, the next iteration adds consecutive element (ex. $\{p_1, p_2, p_4\}$ becomes $\{p_1, p_2, p_4, p_5\}$) if possible, otherwise removes last combination element and increases previous by one (ex. $\{p_1, p_2, p_4\}$ becomes $\{p_1, p_3\}$). Once it discovers a combination which product is greater than $N$, procedure again removes last combination element and increases previous by one. Procedure stops when it meets combination of one element greater than $N$, or when it is $\{p_n\}$.
Now, is there a faster way to do this? I don't think I can improve my algorithm performance enough.