Very divisible subsets
Here is an idea. By factoring the numbers, we are reduced to the following problem:


  Given a set $S$ of vectors in $\mathbb{N}^k$, find a maximum-size subset $T \subseteq S$ such that for every $x \in T$ we have $x \leq \sum_{y \in T - x} y$ (pointwise).


If there is some $x \in S$ and some coordinate $i \in [k]$ such that $x_i &gt; \sum_{y \in S - x} y_i$, then clearly $x_i$ cannot belong to any such set $T$, and we can simply remove it. Keep removing such elements from $S$ until no such elements exist. Then for every $x \in S$ and $i \in [k]$ it is the case that $x_i \leq \sum_{y \in S-x} y_i$, and so the filtered set $S$ is the unique solution.

Let me demonstrate this solution using your example $2,3,4,5,7,8,9,10$. Only 4 prime factors appear here (2,3,5,7), and converting $2^x3^y5^z7^w$ to the vector $xyzw$, we obtain the following vectors:
$$
\begin{align*}
2 &amp;= 1000 \\ 3 &amp;= 0100 \\ 4 &amp;= 2000 \\ 5 &amp;= 0010 \\
7 &amp;= 0001 \\ 8 &amp;= 3000 \\ 9 &amp;= 0200 \\ 10 &amp;= 1010
\end{align*}
$$

We remove 7 due to the 4th coordinate. We then remove 9 due to the 2nd coordinate. We then remove 3 due to the 2nd coordinate. We cannot remove any more numbers, and so are left with the answer 2,4,5,8,10.

The challenge is to implement this greedy algorithm efficiently, which you can do by maintaining the sum of all elements left in the set, and using several priority queues (though perhaps there is a better solution). Details left to you.