Алгоритм Евклида для нахождения НОД

Алгоритм Евклида для нахождения наибольшего общего делителя двух данных чисел заключается в том, чтоб делить большее число на меньшее, а затем делить меньшее на остаток. Так повторяют, пока в остатке не получится или 0, и тогда остаток, получившийся на предыдущем шаге — это и будет НОД.