11
$\begingroup$

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?

$\endgroup$
4
  • 4
    $\begingroup$ You might want to take a look at Section 3.3 of Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices (Heninger et al, Usenix Security 2012). They describe an algorithm for computing pairwise gcd's in $O(n \lg n)$ gcd's, in a certain setting, using product trees and remainder trees. I don't know if it extends to your problem, though. $\endgroup$ – D.W. Jun 27 '14 at 23:22
  • $\begingroup$ Have you tried anything with prime factorizations? $\endgroup$ – Ryan Jul 28 '14 at 12:51
  • 1
    $\begingroup$ Suppose all the numbers are relatively prime but hard to factor (e.g. each $s_i$ is equal to $p_iq_i$ for large distinct primes $p_i,q_i$). Then it seems difficult to avoid checking all pairwise GCDs. (Say I tell you that after checking all pairs but $(s_{n-1},s_n)$ that all the pairwise GCDs are $1$. How could you guess $gcd(s_{n-1},s_n)$ without computing it?) $\endgroup$ – usul Jul 29 '14 at 10:29
  • $\begingroup$ @usul D.W's link is exactly that problem. A huge number, say one billion, encryption keys should all be products of two distinct primes. But we suspect that some encryption keys have a prime factor in common (which would be the gcd of both keys, making both easy to factor). That algorithm lets you find the keys with common factor without calculating n(n-1)/2 gcd's for n = 1 billion. $\endgroup$ – gnasher729 Apr 16 '18 at 21:40
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ This takes exponential time (sqrt(max) is exponential in the length of the input) so it is way worse than other solutions unless the numbers involved are small. $\endgroup$ – D.W. Jan 5 at 2:49
  • $\begingroup$ Again, this algorithm is only more efficient if sqrt(max)/log(max) < N where N is the size of the array. Also, I'm not sure what "length of input" means. Are you referring to N or the max number? $\endgroup$ – timg Jan 5 at 2:55
  • $\begingroup$ I understand that; I'm saying that condition only happens if the numbers $s_1,\dots,s_n$ are small. The length of the input is the number of bits it takes to represent the input. I still don't understand how your algorithm works. Do you mean only prime divisors? There are can be divisors of x larger than sqrt(x). I don't know how you plan to find the largest gcd. $\endgroup$ – D.W. Jan 5 at 2:59
  • 1
    $\begingroup$ All divisors. I will modify my explanation to make this more clear. Also, the number of bits of the entire input does not matter regarding comparing the two approaches. The number of bits in a particular element does. Again, refer to the formula. $\endgroup$ – timg Jan 5 at 3:02
  • 1
    $\begingroup$ No need. I understand now what you are proposing. I missed the key idea for enumerating the divisors, about each divisor larger than $\sqrt{x}$ being paired with one that is smaller. Thank you for the edits. (To help you understand why I mentioned that: the complexity as a function of the length of input is one standard measure of asymptotic running time.) $\endgroup$ – D.W. Jan 5 at 3:21
-2
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ Can you explain your algorithm in words? This is not a programming site. $\endgroup$ – Yuval Filmus Jul 18 '17 at 15:08
  • $\begingroup$ @YuvalFilmus I have added the explanation. Hope this helps. $\endgroup$ – Subhendu Ranjan Mishra Jul 19 '17 at 17:58
  • 2
    $\begingroup$ What if all elements are unique? This doesn't mean that the maximal GCD is 1. Consider for example the set $\{2,4\}$, where the maximal GCD is 2. $\endgroup$ – Yuval Filmus Jul 19 '17 at 18:01
  • $\begingroup$ @YuvalFilmus for every i starting with m till 1 we check if two or more multiples of i are in the set. In this exmaple two multiples of 2 are in the set '2 and 4` . so the answer is 2. The inner while loop checks all the multples of i till m' as m` is the masx of the list. $\endgroup$ – Subhendu Ranjan Mishra Jul 19 '17 at 18:24
  • 2
    $\begingroup$ Well, this is a terrible algorithm. For an array of two numbers $x,y$ of length $n$ bits each, computing the GCD takes polynomial time, whereas your algorithm takes exponential time in the worst case (when the numbers are relatively prime). $\endgroup$ – Yuval Filmus Jul 19 '17 at 18:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.