Effizientes Finden der maximalen paarweisen GCD eines Satzes natürlicher Zahlen

Betrachten Sie das folgende Problem:

Sei eine endliche Teilmenge der natürlichen Zahlen.$S = \{ s_1, s_2, ... s_n \}$

Sei | wobei der größte gemeinsame Teiler von undg c d ( s i , s j ) s i , s j ∈ S , s i ≠ s j } g c d ( x , y ) x $G = \{$ $gcd(s_i, s_j)$$s_i, s_j \in S,$ $s_i \neq s_j \}$$gcd(x,y)$$x$$y$

Finden Sie das maximale Element von .$G$

Dieses Problem kann gelöst werden, indem der größte gemeinsame Teiler jedes Paares unter Verwendung des Euklid-Algorithmus genommen und der größte verfolgt wird.

Gibt es eine effizientere Möglichkeit, dies zu lösen?

Hier ist ein effizienter Algorithmus (in Python ). Die Erklärung finden Sie unten.

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

Erläuterung des obigen Codeausschnitts:

Bei diesem Problem stellen wir Folgendes fest:

1. Das Ergebnis kann nicht mehr als sein max(S)
2. Das Ergebnis ist eine Zahl, die zwei oder mehr Vielfache in dieser Liste enthält S
3. Tatsächlich ist das Ergebnis maxall dieser Zahlen mit der oben erwähnten Eigenschaft.

Mit diesen Beobachtungen führt das Programm Folgendes aus:

1. Machen Sie eine setaus der Liste. As Sets können effizient in gesucht werdenO(log(n))
2. Suchen Sie das Maximum der Liste und speichern Sie es in der Variablen m.
3. Suchen Sie von mbis bis 1zur ersten Zahl, die zwei oder mehr Vielfache im Satz enthält. Die erste gefundene Zahl ist das Ergebnis.

Ich hoffe das ist klar. Bitte lassen Sie mich wissen, wenn Sie eine ausführlichere Erklärung benötigen.