42
правки
Изменения
→Наивный алгоритм
===Наивный алгоритм===
В наивном методе, мы считаем, что нам известны разложения чисел <tex>a</tex> и <tex>b</tex> на простые множители.
<font color=green>// <tex>p</tex> {{---}} множество простых чисел в разложении <tex>a</tex></font>
<font color=green>// <tex>q</tex> {{---}} множество простых чисел в разложении <tex>b</tex></font>
<font color=green>// <tex>\alpha</tex> {{---}} степени простых чисел в разложении <tex>a</tex></font>
<font color=green>// <tex>\beta</tex> {{---}} степени простых чисел в разложении <tex>b</tex></font>
'''function''' <tex>\mathtt{naiveGcd}(p, q, \alpha, \beta):</tex>
<tex>\mathtt{gcd} \leftarrow 1</tex>
<tex>\mathtt{i, j} \leftarrow 0, 0</tex>
'''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{gcd} = \mathtt{gcd} \cdot p_i^{\alpha_i}</tex>
'''else if''' <tex>p_i < q_j:</tex>
<tex>\mathtt{i} \mathrel{+}\mathrel{\mkern-2mu}= 1</tex>
'''else''':
<tex>\mathtt{j} \mathrel{+}\mathrel{\mkern-2mu}= 1</tex>
'''return''' <tex>\mathtt{gcd}</tex>
===Стандартный алгоритм Евклида===
