Алгоритм нахождения НОД

1. **Разложить данные числа на простые множители.** Это значит, представить каждое число в виде произведения простых чисел. 2. **Выписать все простые множители, которые одновременно входят в каждое из полученных разложений.** Иными словами, найти общие простые множители для обоих чисел. 3. **Составить произведение из этих множителей и вычислить его.** Перемножить все общие простые множители. Результат и будет НОД.