Euclidean Algorithm GCD

Algoritmo euclideo animato

Massimo comun divisore.

Utile per ridurre le frazioni

Algoritmo Euclideo visibile

GCD, noto anche come il più grande fattore comune (gcf), il più alto fattore comune (hcf), la più grande misura comune (gcm) o il massimo comune divisore.

Rappresentazione dinamica e geometrica dell'algoritmo.

Algoritmo ricorsivo

E il minimo comune multiplo dedotto da GCD:

lcm (a, b) = a * b / gcd (a, b)

Utile per capire il codice ricorsivo gcd (Algoritmo Euclideo): (Java)

int gcd (int m, int n) {

    if (0 == n) {

        ritorno m;

    }altro{

        return gcd (n, m% n);

    }

}

Aggiunta la visualizzazione geometrica.

Algoritmo eseguito da Denti di Leone provenienti dal vicino Giardino Matematico

Storia dell'algoritmo euclideo

("Il polverizzatore")

L'algoritmo Euclideo è uno dei più vecchi algoritmi di uso comune.

Appare negli Elementi di Euclide (300 aC circa), in particolare nel Libro 7 (Proposte 1-2) e nel Libro 10 (Proposte 2-3).

Secoli dopo, l'algoritmo di Euclide fu scoperto indipendentemente sia in India che in Cina, principalmente per risolvere equazioni diofantee sorte in astronomia e fare calendari precisi.

Alla fine del V secolo, il matematico e astronomo indiano Aryabhata descrisse l'algoritmo come "polverizzatore", forse per la sua efficacia nel risolvere le equazioni diofantee.

Ringraziamenti:

Joan Jareño (Creamat) (aggiunta di lcm)