Trouver efficacement le GCD par paire maximum d'un ensemble de nombres naturels

Considérez le problème suivant:

Soit un sous-ensemble fini des nombres naturels.$S = \{ s_1, s_2, ... s_n \}$

Soit | où est le plus grand diviseur commun de et$G = \{$ $gcd(s_i, s_j)$$s_i, s_j \in S,$ $s_i \neq s_j \}$$gcd(x,y)$$x$$y$

Trouver l'élément maximum de .$G$

Ce problème peut être résolu en prenant le plus grand diviseur commun de chaque paire en utilisant l'algorithme d'Euclide et en gardant une trace du plus grand.

Existe-t-il un moyen plus efficace de résoudre ce problème?

Voici un algorithme efficace (en Python ). Veuillez trouver l'explication ci-dessous.

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

Explication de l'extrait de code ci-dessus:

Nous observons ce qui suit dans ce problème:

1. Le résultat ne peut être supérieur à max(S)
2. Le résultat est un nombre, qui a deux ou plusieurs multiples dans cette liste S
3. En fait, le résultat est maxde tous ces numéros avec la propriété mentionnée ci-dessus.

Avec ces observations, le programme fait ce qui suit:

1. Faites un setde la liste. Comme les ensembles peuvent être recherchés efficacement dansO(log(n))
2. Trouvez le maximum de la liste et stockez-le dans la variable m.
3. À partir de mjusqu'à 1, trouvez le premier nombre qui a deux ou plusieurs multiples dans l'ensemble. Le premier tel nombre trouvé est le résultat.

J'espère que cela est clair. Veuillez me faire savoir si vous avez besoin d'une explication plus détaillée.