最大公约数和最小公倍数的解法

什么是最大公约数和最小公倍数？

• 最大公约数（Greatest Common Divisor，GCD）是指两个或多个整数共有约数中最大的一个。例如，12 和 18 的最大公约数是 6，因为它们都可以被 6 整除，而且没有比 6 更大的约数。
• 最小公倍数（Least Common Multiple，LCM）是指两个或多个整数共有的倍数中最小的一个。例如，12 和 18 的最小公倍数是 36，因为它们都是 36 的倍数，而且没有比 36 更小的公倍数。

如何求最大公约数和最小公倍数？

求最大公约数和最小公倍数的方法有多种，常见的有以下四种：

• 质因数分解法：先把两个整数分别分解成质因数的乘积形式，然后找出它们共有的质因数，并将这些质因数相乘，所得的积就是最大公约数。再将两个整数的所有质因数相乘，所得的积除以最大公约数，就是最小公倍数。
• 辗转相除法：也叫欧几里德算法，是利用两个整数的最大公约数等于其中较小的那个数和两数取模的最大公约数这一性质，即

  gcd(a,b)=gcd(b,amodb)

  ，其中

  a>b

  。具体步骤如下：
  • 用较大数除以较小数，得到余数；
  • 如果余数为0，算法结束，较小数即为最大公约数；
  • 如果余数不为0，用较小数除以余数，重复上述步骤。
• 更相减损法：出自于中国古代的《九章算术》，是利用两个整数的最大公约数等于其中较小的那个数和两数相减的差的最大公约数这一性质，即

  gcd(a,b)=gcd(b,a−b)

  ，其中

  a>b

  。具体步骤如下：
  • 比较两个数的大小，用较大数减去较小数，得到差；
  • 如果差为0，算法结束，两个数相等，它们本身就是最大公约数；
  • 如果差不为0，用较小数和差比较大小，重复上述步骤。
• Stein算法：是结合了辗转相除法和更相减损法的优势以及移位运算的一种高效算法。它利用了移位运算和按位与运算来判断一个整数是否为偶数，并根据以下性质进行计算：
  • 当

    a

    和

    b

    均为偶数时，

    gcd(a,b)=2×gcd(a/2,b/2)=2×gcd(a>>1,b>>1)

  • 当

    a

    是偶数，

    b

    是奇数时，

    gcd(a,b)=gcd(a/2,b)=gcd(a>>1,b)

  • 当

    a

    是奇数，

    b

    是偶数时，

    gcd(a,b)=gcd(a,b/2)=gcd(a,b>>1)

  • 当

    a

    和

    b

    均为奇数时，先比较大小，然后用较大数减去较小数的结果和较小数递归调用函数，即

    gcd(a,b)=gcd(b,a−b)

    ，此时

    a−b

    的结果必然是偶数，又可以继续进行移位运算。

举例说明

下面我们用一个例子来说明这四种方法的具体过程。假设我们要求 36 和 24 的最大公约数和最小公倍数。

• 质因数分解法：

  • 分解质因数：

    36=2×2×3×3，24=2×2×2×3

  • 找出共有的质因数：

    2×2×3

  • 相乘得到最大公约数：

    12

  • 将两个整数的所有质因数相乘：

    36×24=25×34

  • 除以最大公约数得到最小公倍数：

    72

• 辗转相除法：

  • 用较大数除以较小数，得到余数：

    36÷24=1……12

  • 如果余数为0，算法结束，较小数即为最大公约数；如果余数不为0，用较小数除以余数，重复上述步骤：

    24÷12=2……0

  • 最大公约数为

    12

  • 最小公倍数等于两个整数的乘积除以最大公约数：

    36×24÷12=72

• 更相减损法：

  • 比较两个数的大小，用较大数减去较小数，得到差：

    36−24=12

  • 如果差为0，算法结束，两个数相等，它们本身就是最大公约数；如果差不为0，用较小数和差比较大小，重复上述步骤：

    24−12=12

  • 最大公约数为

    12

  • 最小公倍数等于两个整数的乘积除以最大公约数：

    36×24÷12=72

• Stein算法：

  • 如果

    a

    和

    b

    都为0，算法结束，最大公约数为0；如果

    a

    和

    b

    中有一个为0，算法结束，最大公约数为另一个非零数；如果

    a

    和

    b

    都不为0，继续下一步；
  • 如果

    a

    和

    b

    都为偶数，用移位运算和按位与运算判断，然后用右移一位的结果递归调用函数，并将结果乘以2；如果

    a

    是偶数，

    b

    是奇数或者反过来，用移位运算和按位与运算判断，然后用右移一位的

    a

    和原来的

    b

    或者反过来递归调用函数；如果

    a

    和

    b

    都为奇数，先比较大小，然后用较大数减去较小数的结果和较小数递归调用函数；
    • 判断 $$36 (100100) 和 24 (11000) 是否都为偶数：是，则右移一位并递归调用函数，并将结果乘以2；
    • 判断 $$18 (10010) 和 12 (1100) 是否都为偶数：是，则右移一位并递归调用函数，并将结果乘以2；
    • 判断 $$9 (1001) 和 6 (110) 是否都为偶数：否，则判断是否有一个是偶数：是，则右移一位的6和原来的9递归