Мы уже говорили про наибольший общий делитель и наименьшее общее кратное в других статьях. Я показывала быстрые способы их нахождения, но всегда отмечала, что эти способы хорошо работают с небольшими числами. Если у вас число в 4-5 и больше разрядов - нужно искать другой способ. Наступил момент показать один совершенно удивительный и - главное - невероятно способ нахождения наибольшего делителя (НОД, для сокращения дробей) и наименьшего кратного (НОК, для приведения к общему знаменателю) на случай, если цифры у вас большие...

Любая сложная задача всегда может быть разбита на несколько простых задач. Те в свою очередь могут быть разбиты на ещё1 более мелкие задачи. В олимпиадных задачах по программированию очень часто требуется найти НОД(наибольший общий делитель) или НОК(наименьшее общее кратное) двух или более чисел. Это может быть задача по фасовке предметам по ящикам (целочисленное деление) или формирование людей в бригады. Короче там где нужно искать целые числа после деления. Пример двух чисел 6 и 15. Очевидно, что НОД (наибольшим общим делителем) будет число 3...