Как можно найти НОД двух натуральных чисел, используя их разложение на простые множители

Достаточно просто. Надо лишь перемножить множители, которые встречаются в обоих разложениях.

Пример:

а = 2³ * 3 * 5³ * 7²

b = 2² * 5³ * 7

В обоих разложениях присутствуют 2², 5³ и 7. Перемножим:

НОД (а, b) = 2² * 5³ * 7

(с вашего позволения считать не буду. Тут важен был принцип. Он, надеюсь, понятен)