Как найти наибольший общий делитель двух целых чисел?

Каждое из двух целых чисел нужно делить на простые числа до тех пор пока в остатке будет простое число. Возьмём например числа 360 и 1200, 360/2 =180, 180/2=90, 90/2=45, 45/3=15, 15/3=5, 5 - число простое. 360 делится 3 раза на 2, 2 раза на 4 и 1 раз на 5. 1200/2=600, 600/2=300, 300/2=150, 150/2=75, 75/3=25, 25/5=5. 1200 делится 4 раза на 2. Общие делители у этих чисел 3 раза на 2, один раз на 3 и один раз на 5. Перемножив эти общие делители получим наибольший общий делитель, 2*2*2*3*5=120, 360/120=3, 1200/120=10.

А можно воспользоваться алгоритмом Евклида. Он гласит, что наибольший общий делитель двух чисел равен последнему отличному от нуля остатку в алгоритме Евклида.

Например. Найдем НОД(12, 16):

Тогда НОД(16,12)=4