摘要:本文介绍了欧几里得算法,介绍了其用于求两数的最大公因数和最小公倍数的方法。

  1. 欧几里得算法
    欧几里得算法(Euclidean Algorithm)又名辗转相除法。它首次出现于欧几里得的《几何原本》(第VII卷,命题i和ii)中,而在中国则可以追溯至东汉出现的《九章算术》。
    欧几里得算法,可以快速求两数最大公因数(Greatest Common Divisor)的算法,知道了两个数的最大公因数,我们就可以很快的计算出两个数的最小公倍数。

  2. 算法原理
    在本文中,我们约定,使用$gcd(a, b)$表示两个正数$a$、$b$的最大公因数;使用记号$a \bmod b$整数$a$除以$b$的余数;使用记号$a\ |\ b$表示$b \bmod a = 0$,即b被a整除;使用记号$\lfloor a \rfloor$表示不大于a的最大整数。
    基于以上的约定,欧几里得的算法原理可以表示为:
    $$gcd(a, b) = gcd(b, a \bmod b),\ b\neq 0 \tag{*}$$
    这是为什么呢?我们不妨假设$a > b$,先对递推式(*)进行推导(若$a < b$,(*)式在一次运算后会变为$gcd(b, a)$)。
    设:
    $$k = \lfloor \frac{a}{b}\rfloor,\ c = a \bmod b \tag{1}$$
    有:
    $$a = kb + c \tag{2}$$
    根据最大公因数的定义,我们知道:
    $$gcd(a, b) \ |\ a \tag{3}$$
    类似的:
    $$gcd(a, b) \ |\ b \tag{4}$$
    结合(2)(3),有:
    $$gcd(a, b) \ |\ kb + c \tag{5}$$
    由于(4),显然:
    $$gcd(a, b) \ |\ c \tag{6}$$
    根据(1):
    $$gcd(a, b) \ |\ (a \bmod b) \tag{7}$$
    通过(7),我们知道$gcd(a, b)$与$gcd(b, a \bmod b)$是等价的,即:
    $$gcd(a, b) = gcd(b, a \bmod b), \tag{*}$$
    当然,这个递归算法是有终止条件的。当$b = 0$的时候,$a$即为所求的最大公因数。
    这样,欧几里得算法被我们证明是正确的。

  3. 算法实现
    基于以上的证明,我们就可以通过欧几里得算法(*),来计算两个数的最大公因数。我们可以递归地计算:

    int gcd(int a, int b)
    {
        if (b)
        {
            return gcd (b, a % b);
        }
        else
        {
            return a;
        }
    }
    

    代码非常简单,我们甚至能在一行内写完,如:

    int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
    
  4. 最小公倍数(Least Common Multiple)
    在本文中,我们使用记号$lcm(a, b)$表示数$a$、$b$的最小公倍数。
    根据最大公因数的定义,我们有:
    $$\exist m\in \N,\ a = m\ gcd(a, b)$$
    类似的:
    $$\exist n\in \N,\ b = n\ gcd(a, b)$$
    显然,$m$与$n$互质。
    根据最小公倍数的定义,有:
    $$lcm(a, b) = m\ n\ gcd(a, b)$$
    所以:
    $$a\ b = lcm(a, b)\ gcd (a, b)$$
    即:两正整数之积等于两数最大公因数和最小公倍数之积
    基于这个原理,我们求出两个正整数的最小公倍数:
    $$lcm(a, b) = \frac{a\ b}{gcd(a, b)}$$
    代码如下:

    int lcm(int a, int b)
    {
        return a / gcd(a, b) * b;
    }
    
  5. 习题
    1. 最大公因数与最小公倍数问题
    2. 不使用递归,重写gcd这个函数(据说这样的性能会比递归写法要好一些)。
  6. 参考文献
    1. 辗转相除法
    2. Euclidean Algorithm
最后修改日期: 2019年10月10日

作者

0 0 投票数
文章评分
订阅评论
提醒
0 评论
内联反馈
查看所有评论