Very divisible subsets I've recently come across the following problem.

We're given up to $10^4$ distinct positive integers $a_1,\dots , a_n$, each of them below $10^6$. Let's call a subset $S \subset \{a_1,\dots,a_n\}$ a very divisible subset if any number in this subset divides the product of other numbers in this subset.

The task is to find the largest such subset. It is guaranteed that there is at least one with at least $3$ elements. If there are several such subsets we can output any of them. For example if we're given numbers $2, 3, 4, 5, 7, 8, 9, 10$ then the algorithm might output $2, 4, 5, 8, 10$.

It's neither a homework nor an ongoing contest. I'm just curious how to solve it. Unfortunarely for now i can't see any solution better than brute force through all the subsets. And such approach is unfeasible under given limitations. Any ideas will be highly appreciated. Thanks in advance.

P.S.
Here's an original statement of this problem: https://www.e-olymp.com/en/problems/7331
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.