The Euclidean Algorithm
欧几里得算法（the Euclidean Algorithm） 是寻找 最大公约数 的快速算法，采用 递归 算法。
算法
定义函数 GCD(A, B)：
- 当
A = 0，此时GCD(A, B) = B - 当
B = 0，此时GCD(A, B) = A - 利用整除和取模，计算得
A = B * Q + R获取余数 - 此时
GCD(A, B) = GCD(B, R)，递归
代码
pub fn gcd(a: u64, b: u64) -> u64 {
if b == 0 {
return a;
}
gcd(b, a%b)
}
Khanac Ademy
The Euclidean Algorithm for finding GCD(A,B) is as follows:[1]
- If A = 0 then GCD(A,B)=B, since the GCD(0,B)=B, and we can stop.
- If B = 0 then GCD(A,B)=A, since the GCD(A,0)=A, and we can stop.
- Write A in quotient remainder form (A = B⋅Q + R)
- Find GCD(B,R) using the Euclidean Algorithm since GCD(A,B) = GCD(B,R)
Prove
GCD(A, B) = GCD(B, R)
To prove that GCD(A, B) = GCD(B, R) we first need to show that GCD(A, B) = GCD(B, A - B).