42
правки
Изменения
→Наивный алгоритм
'''while''' <tex>\mathtt{i} < p\mathtt{.length()}</tex> '''and''' <tex>\mathtt{j} < q\mathtt{.length()}:</tex>
'''if''' <tex>p_i</tex> == <tex> q_j:</tex>
<tex>\mathtt{t} \leftarrow \min(\alpha_i, \beta_j)</tex> <tex>\mathtt{gcd} = \mathtt{gcd} \cdot p_i^{\alpha_imathtt{t}}</tex>
'''else if''' <tex>p_i < q_j:</tex>
<tex>\mathtt{i} \mathrel{+}\mathrel{\mkern-2mu}= 1</tex>
<tex>\mathtt{j} \mathrel{+}\mathrel{\mkern-2mu}= 1</tex>
'''return''' <tex>\mathtt{gcd}</tex>
Корректность алгоритма следует из того, что он по сути просто делает слияние двух упорядоченных массивов (<tex>p</tex> и <tex>q</tex>), только результат записывает не в массив, а агрегирует в переменной <tex>\gcd</tex>
===Стандартный алгоритм Евклида===
