Remove divisors from a set of integers
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.