Efficiently finding the maximum pairwise GCD of a set of natural numbers

Question

Consider the following problem:

Let $S = \{ s_1, s_2, ... s_n \} $ be a finite subset of the natural numbers.

Let $G = \{$ $\gcd(s_i, s_j) \mid s_i, s_j \in S,$ $ s_i \neq s_j \}$ where $\gcd(x,y)$ is the greatest common divisor of $x$ and $y$

Find the maximum element of $G$.

This problem can be solved by taking the greatest common divisor of each pair using Euclid's algorithm and keeping track of the largest one.

Is there a more efficient way of solving this?

Answer 1

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

Answer 2

For this problem, there exists a simple solution of just counting all divisors for each number, then checking if each divisor matches with a previously counted divisor.

Counting a number's divisors can be done in $\sqrt{x}$ where $x$ is the number. Specifically, all divisor in a given number x can be expressed as divisor pairs, where $z\cdot y = x$ and $z < \sqrt{x} < y$ except if $z = y = \sqrt{x}$. This means that by looping through the range $[1,\sqrt{x}]$, all divisors (both prime and non-prime) of $x$ can effectively be found.

Checking and storing a divisor could be done with a HashSet or some equivalent.

This algorithm yields an $\mathcal{O}(n\sqrt{\mathrm{max}})$ solution, where $\mathrm{max}$ is the max number in the array.

Comparing this to your $\mathcal{O}(n^2 \log(n))$ solution, this algorithm is more efficient if $n \sqrt{\mathrm{max}}$ < $n^2 \log(\mathrm{max})$, which simplifies to if $\sqrt{\mathrm{max}}/\log(\mathrm{max}) < N$.

Answer 3

Here is an efficient algorithm (in Python). Please find the explanation below.

def max_gcd_pair(S):
    # Assumption 1: S is the list of numbers
    # Assumption 2: There are no duplicates in S

    s = set(S)
    m = max(S)

    res = 0
    i = m

    while(i > 0):
        a = i
        cnt = 0
        while (a<=m): # a maxed at max of the list
            if a in s:   
               cnt += 1
            a += i

        if cnt >= 2:  # we have found the result
            res = i
            break

        i = i -1 

    return res

Explanation of the above code snippet :

We observe the following in this problem:

1. The result can not be more than max(S)
2. The result is a number, that has two or more multiples in this list S
3. In-fact the result is max of all such numbers with the property mentioned above.

With these observations, the program does the following:

1. Make a set of the list. As sets can be searched efficiently in O(log(n))
2. Find the max of the list and store it in the variable m.
3. Starting from m till 1, find the first number that has two or more multiples in the set. The first such number found is the result.

I hope this is clear. Please let me know if you need a more detailed explanation.