Алгоритм Евклида
Алгоритм Евклида — эффективный
алгоритм для нахождения
наибольшего общего делителя двух
целых чисел (или
общей меры двух
отрезков). Алгоритм назван в честь
греческого математика Евклида (III век до н. э.), который впервые описал его в VII
и X
книгах «
Начал». Это один из старейших численных алгоритмов, используемых в наше время.
Вспомним математику.
Наибольший общий делитель двух натуральных чисел (НОД) - это самое большое натуральное число, на которое они делятся нацело.
Например, у чисел 12 и 18 имеются общие делители: 2, 3, 6. Наибольшим общим делителем является число 6. Это записывается так: НОД(12, 18) = 6
В программировании есть несколько реализаций алгоритма Евклида. Приведем описание одной из них в виде блок-схемы.
Попробуйте реализовать данный алгоритм.