数学算法：求最大公约数 gaunthan Posted on Dec 1 2016 ? Algorithm ? ## 最大公约数的定义 > 两个整数$a$和$b$的最大公约数(GCD)定义为能除尽这两个数的那个最大的整数。如8和4的最大公约数就是4。 ## 欧几里德算法 找出两个整数的GCD的一种方法是对它们做因数分解，并从中找出公共因子。但求GCD还存在着一个更高效、优美的著名算法：*欧几里德算法*。 这一算法的基于这样的思想： > 如果$r$是$a$除以$b$的余数，那么$a$和$b$的公约数正好也是$b$和$r$的公约数，即等式： $$ GCD(a, b) = GCD(b, r)$$ 这就把一个GCD的计算问题连续地归约到越来越小的整数对的GCD的计算问题。例如： GCD(206, 40) = GCD(40, 6) = GCD(6, 4) = GCD(4, 2) = GCD(2, 0) = 2 可以证明，从任意两个整数开始，反复执行这种归约，最终将产生出一个数对，其中的第二个数是0，此时的GCD就是另一个树。这一计算GCD的方法称为欧几里德算法。 欧几里德算法所需的步数是对数增长的。 ## 编码实现 为了清晰性，下面的编码实现使用的是尾递归的方式，但你总可以将其转化为迭代方式。 ### Scheme ```scheme (define (gcd a b) (if (= b 0) a (gcd b (remainder a b)))) ``` `remainder`是scheme的取余函数，一般解释器自带。 ### C++ ```cpp template<typename T, typename U> T Gcd(const T& a, const U& b) { if(b == 0) return a; return Gcd(b, a % b); } ``` 赏 Wechat Pay Alipay 数学算法：素数检测 决策树学习与ID3算法实现
