Remove divisors from a set of integers

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.)

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.

StackExchange Computer Science Q#13153, answer score: 3