Euclidean Algorithm GCD

Algoritmo Euclidiano Animado

Maior divisor comum.

Útil para reduzir frações

Algoritmo Euclidiano Visível

GCD, também conhecido como o maior fator comum (gcf), fator comum mais alto (hcf), maior medida comum (gcm) ou o divisor comum mais alto.

Representação dinâmica e geométrica do algoritmo.

Algoritmo recursivo

E Múltiplos Múltiplos Comum deduzidos do GCD:

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

Útil para entender o código recursivo do gcd (Euclidean Algorithm): (Java)

int gcd (int m, int n) {

    if (0 == n) {

        return m;

    }outro{

        retorno gcd (n, m% n);

    }

}

Adicionado visualização geométrica.

Algoritmo executado por Dandelions que vem do jardim matemático próximo

História do Algoritmo Euclidiano:

("O Pulverizador")

O algoritmo euclidiano é um dos mais antigos algoritmos de uso comum.

Aparece nos Elementos de Euclides (c. 300 aC), especificamente no Livro 7 (Proposições 1–2) e no Livro 10 (Proposições 2–3).

Séculos mais tarde, o algoritmo de Euclides foi descoberto independentemente tanto na Índia quanto na China, principalmente para resolver as equações diofantinas que surgiram na astronomia e fazer calendários precisos.

No final do século 5, o matemático e astrônomo indiano Aryabhata descreveu o algoritmo como o "pulverizador", talvez por causa de sua eficácia na solução de equações diofantinas.

Agradecimentos:

Joan Jareño (Creamat) (adição de lcm)