42
правки
Изменения
→Стандартный алгоритм Евклида
Проще сформулировать алгоритм Евклида так: если даны натуральные числа <tex>a</tex> и <tex>b</tex> и, пока получается положительное число, по очереди вычитать из большего меньшее, то в результате получится НОД.
Таким образом, реализация стандартного алгоритма Евклида, достаточно проста:
'''function''' <tex>\mathtt{euclideanGcd}(\mathtt{a, b}):</tex>
'''while''' <tex>\mathtt{b} \neq 0:</tex>
<tex>\mathtt{t} \leftarrow \mathtt{b}</tex>
<tex>\mathtt{b} \leftarrow \mathtt{a} \bmod \mathtt{b}</tex>
<tex>\mathtt{a} \leftarrow \mathtt{t}</tex>
'''return''' <tex>\mathtt{a}</tex>
===Расширенный алгоритм Евклида===
