Efficiently finding the maximum pairwise GCD of a set of natural numbers
Solution 1
Time Complexity: $\mathcal{O}(n\sqrt{\max(s_i)})$
Maintain an array, $\texttt{cnt}$, to store the count of divisors. For each $s_i$, find its divisors and for each $u$ in those divisors, increment $\texttt{cnt}[u]$ by one. The greatest GCD shared by two elements in $S$ will be the greatest $u$ where $\texttt{cnt}[u] &gt; 2$.
For each $s_i$, we only need to check up to $\sqrt{s_i}$ for its divisors, so the complexity is $\mathcal{O}(n\sqrt{\max(s_i)})$.
Solution 2
Time Complexity: $\mathcal{O}(\max(s_i)\log(\max(s_i)))$
Given a value $x$, we can check whether there exists a pair with GCD equal to $x$ by counting all the multiples of $x$ in $S$ and checking whether that count is at least 2.
With that information, loop through all possible values of $x$ and keep the maximum one with at least two multiples in $S$. This works in $\mathcal{O}(\max(s_i)\log(\max(s_i)))$ time since
$$
\sum_{x = 1}^{\max(s_i)} \frac{\max(s_i)}{x} \approx \max(s_i)\log(\max(s_i)).
$$