Представьте, что вы заказываете плитку для ванной. Размер стены — ровно 258 см в высоту и 180 см в ширину. Вы хотите уложить плитку самого большого размера, чтобы не резать её и минимизировать швы. Какой максимальный размер квадратной плитки подойдёт? Для решения задачи требуется найти самое большое число, которое делит два других. Первое, что приходит в голову — разложить их на множители. Это работает, но становится невыносимо долгим для больших чисел. Но есть другой путь, известный ещё со времен Древней Греции: простой, элегантный и не требующий никакой факторизации...

Для иллюстрации основных алгоритмических конструкций в информатике и программировании часто применяют алгоритм Евклида. Применяя этот алгоритм, находят наибольший общий делитель двух целых чисел. Благодаря своей простоте и наглядности этот алгоритм не теряет популярности и по сей день. В математике известен конструктивный алгоритм определения наибольшего общего делителя двух целых чисел, который носит название алгоритма Евклида. Греческий ученый математик Евклид первым описал этот алгоритм в своем научном трактате «Начала»...