Euclidean Algorithm GCD

Анимированный евклидовой алгоритм

Наибольший общий делитель.

Полезно для сокращения фракций

Видимый евклидовы алгоритм

GCD, также известный как наибольший общий коэффициент (gcf), старший общий коэффициент (hcf), наибольшая общая мера (gcm) или старший общий делитель.

Динамическое и геометрическое представление алгоритма.

Рекурсивный алгоритм

И наименьшее общее число, выведенное из GCD:

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

Полезно для понимания рекурсивного кода gcd (евклидова алгоритма): (Java)

int gcd (int m, int n) {

    если (0 == п) {

        return m;

    } Еще {

        return gcd (n, m% n);

    }

}

Добавлена ​​геометрическая визуализация.

Алгоритм, выполненный Одуванниками, исходящими из близлежащего Математического сада

История евклидова алгоритма:

(«Пульверизатор»)

Евклидовой алгоритм является одним из самых старых алгоритмов в общем использовании.

Он появляется в Элементах Евклида (около 300 г. до н.э.), в частности в Книге 7 (Предложения 1-2) и в Книге 10 (Предложения 2-3).

Спустя столетия алгоритм Евклида был обнаружен независимо как в Индии, так и в Китае, прежде всего для решения диофантовых уравнений, возникших в астрономии и создании точных календарей.

В конце пятого века индийский математик и астроном Ариабхата описал алгоритм как «пульверизатор», возможно, из-за его эффективности в решении диофантовых уравнений.

Подтверждения:

Joan Jareño (Creamat) (добавление lcm)