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

Несколько способов найти общий делитель двух чисел без перебора всех делителей:

1. Метод разложения на простые множители. 12 Нужно разложить числа на простые множители, подчеркнуть общие простые множители и найти произведение подчёркнутых простых множителей у одного числа — это и будет наибольший общий делитель (НОД). 12
2. Алгоритм Евклида. 12 Из большего числа нужно вычесть меньшее число. 1 Если получается нуль, то числа равны друг другу и будут являться НОД. 1 Если результат вычитания не равен нулю, то большее число заменяется на результат вычитания, и процесс повторяется снова. 1
3. Алгоритм Евклида с делением. 3 Большее число делится на меньшее. 3 Меньшее число делится на остаток, который получается после деления. 3 Первый остаток делится на второй остаток, второй остаток делится на третий и так далее. 3 Деление продолжается до тех пор, пока в остатке не получится нуль. 3 Последний делитель и есть наибольший общий делитель. 3