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

Надо разложить числа на простые множители. Например: 148. 148 делится на 2. Получается 74. 74 тоже делится на 2 . Получится 37. 37 - это простое число, поэтому оно делится тоолько на себя. Получится 1. 1 - не составное и не простое число, поэтому деление первого числа окончено. выписуем пример 148=2*2*37. Теперь делаем то же самое со вторым числом - например 8. 8 делим на 2, почается 4. 4 тоже делим на 2 - получится 2. 2 простое число, делим его само на себя. получится 1. 8=2*2*2. Чтобы вычислить НОД этих чисел надо найти одинаковые множители - в данном случае 2*2. НОД(148; 8) = 2*2=4