НОД и НОК чисел

Наибольший общий делитель - это наибольшее положительное целое число, на которое делятся без остатка заданные числа.

Наименьшее общее кратное чисел - это наименьшее число которое можно разделить на все заданные числа без остатка. 

Как найти НОД

1. Метод перебора делителей
   Этот метод может быть трудоемким для больших чисел.
   Способ заключается в подборе все делителей чисел и выбора наибольшего из общих.

   Пример:
   Найдем НОД для чисел 12 и 18.
     Делители числа 12: 1, 2, 3, 4, 6, 12.
     Делители числа 18: 1, 2, 3, 6, 9, 19.
     Общие делители 1, 2, 3, 6.
   Ответ:НОД(12,18) = 6.

2. Разложение на простые множители
   Суть метода представить каждое число в виде умножения простых чисел. 
   Способ хорошо подходит для небольших чисел и может найти НОД для нескольких чисел одноврменно.
   Алгоритм:
     Разложите каждое из чисел на множители методом деления.
     Найдите все общие множители - это такие множители которые есть в каждом из заданных чисел.
     Из Них выберите множители у которых наименьшая степень.
     Перемножьте их между собой и получится НОД.
   Пример:
   НОД(12,18)  

   Число		Множители		В эксп. форме
   12	=	2×2×3	=	22 × 31
   18	=	2×3×3	=	21 × 32

   Общие множители с минимальными степенями:  2¹ * 3¹ = 6
3. Алоритм Евклида
   Самый удобный метод. Хорошо подходит для больших чисел. Но только для двух чисел за один расчет.
   Алгоритм:
     Делим большее число на меньшее и находим остаток.
     Делим меньшее из чисел на остаток от предыдущего деления.
     Потовряем процесс до тех пор пока остаток от деления не станет равен нулю.
     НОД равен последнему ненулевому остатку.
     Если при первом делении остаток ноль, то НОД равен меньшему из чисел. 
   Пример:

   Деление	Частное	Остаток
   18÷12 =	1	6
   12÷6 =	2	0

    НОД(12,18)  = 6

Как найти НОК

1. Через известный НОД
   Самый простой и доступный метод. Однако для его расчета требуется знание НОД и возможен только для двух чисел.
   Метод основан расчете по следующей формуле:

   $НОК=\frac{\left|a·b\right|}{НОД}$
   где a и b  - заданные числа.

   Пример:
   Отыщем НОК для чисел 12 и 18
   Сначала определим НОД(12,18) = 6
   $НОК=\frac{12·18}{6}=36$
2. Метод разложения на простые множители
   Суть метода разложить число на несколько простых чисел - множителей.
   Способ подходит для любого количества чисел.
   Пример:
   Найдем НОК для чисел 12 и 18
     Разложим эти числа на простые множители:

   Число		Множители		В эксп. форме
   12	=	2×2×3	=	22 × 31
   18	=	2×3×3	=	21 × 32

       Если есть повторяющиеся множители то выберем один с наибольшей степенью. Такие множители отмечены зеленым.
       Перемножение всех уникальных множителей с наивысшей степенью между собой даст НОК заданных чисел.

   22 × 32

   =

   36