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

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

а = 2³ × 3 × 5³ × 7²
b = 2² × 5³ × 7

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

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

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