欧几里得算法

大家好，欢迎来到IT知识分享网。

• 欧几里得算法

　　在数学中，辗转相除法，又称欧几里得算法（英语：Euclidean algorithm），是求最大公约数的算法。两个数的最大公约数就是能够同时整除他们的最大正整数。辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。例如，252和105的最大公约数是21（252 = 21 x 12; 105 = 21 x 5 )；因为 252 − 105 = 21 × (12 − 5) = 147 ，所以147和105的最大公约数也是21。在这个过程中，较大的数缩小了，所以继续进行同样的计算可以不断缩小这两个数直至余数为零。这时，所剩下的还没有变成零的数就是两数的最大公约数。由辗转相除法也可以推出，两数的最大公约数可以用两数的整数倍相加来表示，如 21 = 5 × 105 + (−2) × 252 。这个重要的结论叫做裴蜀定理。

　　两个数的最大公约数通常写成GCD(a, b)。如果GCD(a, b) = 1，则称a和b互素。令g = GCD(a, b)。由于a和b都是g的整数倍，所以可以写成a = mg、b = ng，并且不存在更大的整数G > g使等式成立。为了使g尽可能大，就要使a和b中所有公约数都提取出来归入g中，所以自然数m和n一定互素，并且a和b的最大公约数g可以被a和b的所有其他公因数c整除。

　　三个数的最大公约数的定义和两个数的相同，即是它们共有的素因数的积，它们或者也可以按下式计算：

　　GCD(a, b, c) = GCD(a, GCD(b, c)) = GCD(GCD(a, b), c) = GCD(GCD(a, c), b).

所以，欧几里得的辗转相除法实际可以计算任意多整数的最大公约数。

• 辗转相除法计算过程

　　辗转相除法是一种递归算法，每一步计算的输出值就是下一步计算时的输入值。设k表示步骤数（从0开始计数），算法的计算过程如下：

　　每一步的输入是都是前两次计算的非负余数r_k−1和r_k−2。因为每一步计算出的余数都在不断减小，所以，r_k−1小于r_k−2。在第k步中，算法计算出满足以下等式的商q_k和余数 r_k：

r_k−2 = q_k r_k−1 + r_k

其中0 ≤ r_k < r_k−1。也就是r_k−2要不断减去r_k−1直到比r_k−1小。

为求简明，以下只说明如何求两个非负整数a和b的最大公约数（负数的情况是简单的）。在第一步计算时（k = 0），设r₋₂和r₋₁分别等于a和b，第2步（此时k = 1）时计算r₋₁（即b）和r₀（第一步计算产生的余数）相除产生的商和余数，以此类推。整个算法可以用如下等式表示： : a = q₀ b + r₀

b = 
q
₁ 
r
₀ + 
r
₁

r
₀ = 
q
₂ 
r
₁ + 
r
₂

r
₁ = 
q
₃ 
r
₂ + 
r
₃

…

如果有a < b，算法的第一步实际上会把两个数字交换，因为这时a除以b所得的商q₀会等于0，余数r₀则等于a。然后，算法的第二步便是把b除以a，再计算所得之商和余数。所以，对于k ≥ 0总有r_k<r_k−1，即运算的每一步中得出的余数一定小于上一步计算的余数。

由于每一步的余数都在减小并且不为负数，必然存在第N步时r_N等于0，使算法终止，r_N−1就是a和b的最大公约数。其中N不可能无穷大，因为在r₀和0之间只有有限个自然数。　

• 辗转相除法计算机实现

　　Rust实现：

 1 fn gcd(x: isize, y: isize) -> Option<isize> {
 2     match (x,y) {
 3         (0, 0)         => None,
 4         (a, 0)         => Some(a.abs()),
 5         (mut a, mut b) => { 
 6             while b != 0 {
 7                 let t = b;
 8                 b = a % b;
 9                 a = t;
10             }
11 
12             Some(a.abs()) 
13         },
14     }
15 }

　Rust测试代码：

1     #[test]
2     fn gcd_works() {
3         assert_eq!(gcd(3,4), Some(1));
4         assert_eq!(gcd(10,5), Some(5));
5         assert_eq!(gcd(1005,50), Some(5));
6         assert_eq!(gcd(99977,777), Some(1));
7     }