344
правки
Изменения
→Стандартный алгоритм Евклида
Таким образом, реализация стандартного алгоритма Евклида, достаточно проста:
'''function''' <tex>\mathtt{euclideanGcd}(\mathtt{a, b}):</tex> '''while''' b <tex>\mathtt{b} \neq 0:</tex>0 : t <tex>\mathtt{t} \leftarrow \mathtt{b}</tex>b b <tex>\mathtt{b} \leftarrow \mathtt{a} \bmod \mathtt{b}</tex>a mod b a <tex>\mathtt{a} \leftarrow \mathtt{t}</tex>t '''return''' <tex>\mathtt{a}</tex>
Мы получили очень простой алгоритм, который считает НОД за логарифмическое время. However, we can do better.
