Given a set $S$, its multiplicative closure is the set $$ \mathcal{M}(S) = \{s_1s_2\cdots s_k: k\in\mathbb{N},s_i\in S\} $$ of products of zero or more elements of $S$. So the multiplicative closure of $\{2,3\}$ is the set of integers of the form $2^m3^n,$ for example.
I'm looking for an efficient algorithm to compute the number of elements of $\mathcal{M}(S)$ up to a given bound $x,$ given a finite set $S$ of positive integers. You may assume (it is true in my case, and simplifies the problem) that each element of $\mathcal{M}(S)$ has a unique factorization in $S$. In my case $S$ is small (150-250 elements) and $x$ is large ($10^{35}$ to $10^{50}$ or more).
A naive algorithm would construct all of the numbers and count them. This is slow, and more importantly consumes a lot of memory.
A better approach (dynamic programming) is to split the set roughly in half, let's say into $S_1$ and $S_2$, and construct the multiplicative closures of both. Then each element of $\mathcal{M}(S)$ is a product of an element of $\mathcal{M}(S_1)$ and an element of $\mathcal{M}(S_2)$, and by the special property no other product is equal to this value. So you can iterate through one of these, let's say $\mathcal{M}(S_1)$, and for each $m$ in that set the number of products which are at most $x$ is the number of elements in $\mathcal{M}(S_2)$ which are at most $x/m.$ This can be determined with a binary search.
Is there a way to push this method further? Is there a completely different approach which is more efficient? Is there literature I can read?
