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

Достаточно просто. Надо лишь перемножить множители, которые встречаются в обоих разложениях. Пример: а = 2³ × 3 × 5³ × 7² b = 2² × 5³ × 7 В обоих разложениях присутствуют 2², 5³ и 7. Перемножим: НОД(а, b) = 2² × 5³ × 7 (с вашего позволения считать не буду. Тут важен был принцип. Он, надеюсь, понятен)