欧几里得算法
介绍
欧几里德算法,又叫做辗转相除法,用于计算两个正整数a,b的最大公约数(the greatest common divisor)。
计算公式
$$
gcd(a,b)=gcd(b,a\mod b)
$$
证明
第一步:不妨假设 $c=gcd(a,b)$,则 $a=mc$,$b=nc$,其中 $m,n∈z$
第二步:取 $r=a-kb=(m-nk)c$ ,其中$k∈z$,易得 $c$ 也是 $r$ 的因子
第三步:而 $r \mod b=(a-kb)\mod b=a \mod b$,即 c 也是 a mod b 的一个因子
从而 $c = gcd(a,b) = gcd(b,a \mod b)$,结论得证
代码
C++版本
1 |
|
除此之外,还可以用递归来定义此函数
python版本
- 使用math库中带的gcd函数
1 |
|
- 手写GCD
1 |
|
欧几里得算法
https://serendipity565.github.io/posts/ba3cf0836f20/