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