Remove divisors from a set of integers

Question

I have a set $S$ of integers. I want to remove all elements of $S$ that are divisors of another element of $S$. In other words, I want to compute $T = \{y \in S : \forall d \in S . d \nmid y \}$.

How do I do this efficiently?

I can see how to do it in $\Theta(|S|^2)$ time, by examining all pairs of elements of $S$ and keeping only the ones that don't have any divisor in $S$. Can it be done substantially faster? (For simplicity, I'm willing to assume that all standard integer operations---addition, multiplication, division, etc.---can be done in $O(1)$ time. Yes, I know this is an imperfect approximation, but if it makes your answer cleaner, I'm fine with it.)

Answer 1

Let me first repeat my remark: in the application you have in mind (finding the maximal LCM of a partition of $n$), you can assume that the elements of $S$ come factored, and so can represent them as vectors of non-zero integers corresponding to the powers of the various primes. The problem of computing all maxima in this setting has been considered by Kung, Luccio and Preparata, but they only give efficient algorithms in the case when the dimension (number of different primes) is constant, which is not your case. They also give a lower bound of $\Omega(n\log n)$. The problem has took up in the database literature under the name of Skyline - perhaps these people have practical algorithms which could be useful here.

Answer 2

Here's a divide-and-conquer algorithm that in principle might improve slightly upon the naive approach, but in practice doesn't seem much better. It is inspired by one of the techniques used by Kung, Luccio, and Preparata, but without adopting some of their other clever methods.

• If the set $S$ is small (say, fewer than 10 elements), use the naive approach. Otherwise, initially set $p=2$ and do the following:

• Split the set $S$ into $S_0,S_1$, where $S_0 = \{x \in S : p \mid x\}$ is the subset of elements that are a multiple of $p$ and $S_1 = \{y \in S : p \nmid y\}$ is the rest of $S$.

• Recursively compute the solution for each of $S_0,S_1$, obtaining $T_0,T_1$, but replacing $p$ with the next prime after $p$ for the recursive call. (Thus, each recursive call advances to the next prime; if you are $i$ deep in the recursion tree, you use the $i$th prime as your $p$.)

• Now we want to merge $T_0,T_1$. To do this, we note that no element of $T_0$ can be a divisor of $T_1$, so we only need to check each element of $T_1$ to see whether it is a divisor of $T_0$. The running time for the merge operation is $O(|T_0| \cdot |T_1|)$.

However, this doesn't seem to do all that much better than the naive approach, sadly.

Reference:

• On finding the maxima of a set of vectors. H.T. Kung, F. Luccio, F.P. Preparata. Journal of the ACM, vol 22 no 4, pp.469--476, 1975.