Алгоритм Евклида - НОД

Формальный способ находить Наибольший общий делитель (алгоритм Евклида).

Если ваш НОД больше единицы, значит разделить оба числа на него и перемножить НОД на два остатка от деления, получите НОК. Если НОД равен 1, то значит числа взаимно простые и их просто надо перемножить. Это чтобы не заморачиваться с делимостями.

Алгоритм вот:
1 Большее число делим на меньшее.
2 Если делится без остатка, то меньшее число и есть
3 Если есть остаток, то большее число заменяем на остаток от деления.
4 Переходим к пункту 1.

Пример:
Найти НОД для 30 и 18.
30/18 = 1 (остаток 12)
18/12 = 1 (остаток 6)
12/6 = 2 (остаток 0). Конец: НОД - это делитель. НОД (30, 18) = 6

А как найти наименьшее общее кратное (НОК) тех же чисел? Нет ли и для этого какого-нибудь способа, не требующего предварительного разложения этих чисел на простые множители? Оказывается, есть, и притом очень простой. Нужно перемножить эти числа и разделить произведение на найденный нами наибольший общий делитель(НОД). В данном примере произведение чисел равно 98441. Делим его на 7 и получаем число 14063. НОК(343,287) = 14063.

http://festival.1september.ru/articles/604233/