查看“欧几里得算法”的源代码

'''欧几里得算法'''又称'''辗转相除法'''，是求最大公约数的算法。

<math>
\forall a,b, \in N,b\not = 0, gcd(a,b) = gcd(b, a \;\mathrm{mod}\; b)
</math>
<math></math>
== 证明 ==
* 若 <math>a < b</math>
*: <math>gcd(b, a \;\mathrm{mod}\; b) = gcd(b, a) = gcd(a, b)</math> ，命题成立
* 若 <math>a \geq b</math>
*: 不妨设 <math>a=q*b+r</math>，其中 <math>0 \leq r < b</math>。显然<math>r=a \;\mathrm{mod}\; b</math>。
*: 对于 a,b 的任意公约数d，因为 <math>d|a,d|q*b</math>，故 <math>d|(a-qb)</math>，即 <math>d|r</math>，因此d也是b,r的公约数，反之亦成立。
*: 故a,b的公约数集合与 <math>b,a \;\mathrm{mod}\; b</math> 的公约数集合相同。于是它们的最大公约数自然也相等。

证毕。

== 实现 ==
<syntaxhighlight lang="c" line>
int gcd(int a, int b) {
	return b ? gcd(b, a % b) : a;
}
</syntaxhighlight>

== 注释 ==
<syntaxhighlight lang="c" line>
// 计算两个整数的最大公约数
int gcd(int a, int b) {
    // 如果b不为0，则递归调用gcd函数，参数为b和a除以b的余数
    return b ? gcd(b, a % b) : a;
}
</syntaxhighlight>

== 参考资料 ==
# 算法竞赛进阶指南，李煜东，143页
[[Category:数学]]