使用辗转相除法(Euclidean algorithm)求两个数的最大公约数(Greatest common divisor)
以下都是我个人的理解,
如果有哪里不对的地方还请赐教(
记住一个公式是 $$ a = b \cdot q + r $$
其中a和b就是要被求GCD的两个数字.
举个例子,比如我要求gcd(90,65),则得出: $$ 90 = 65 \cdot q + r $$
那么经过计算式子1,得到 $ q = 1 $ ,$ r = 15 $,即 $ 90 = 65 \cdot 1 + 15 $.
接下来,把 $ 90 = 65 \cdot 1 + 15 $ 中的 b 赋值予 a ,r 赋值予 b ,再