А теперь к настоящим алгоритмам, а не использованию уже написанных в стандартной библиотеке. Читаем условие задачи: Алгоритм Евклида - это, действительно, эффективный способ вычисления наибольшего общего делителя двух чисел. Но та версия, которую изучил Дима из условия задачи является неоптимальной. Давайте посмотрим на примере. Если даны два числа 1000000 и 12, то шаг 4 будет выполняться очень много раз (83333), после чего a будет равно 4, а b - 12 (затем, они, конечно, поменяются местами). На примере мы можем заметить, что 1000000 = 83333 * 12 + 4, или в общем виде a = k * b + r...

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