最大公约数(Greatest Common Divisor,简称 GCD)是指两个或多个整数共有约数中最大的
一个。例如,对于整数 12 和 18,它们的最大公约数是 6。
最小公倍数(Least Common Multiple,简称 LCM)则是指能被两个或多个整数共同整除的最
小正整数。例如,对于整数 12 和 18,它们的最小公倍数是 36。
求解最大公约数和最小公倍数的方法有很多种,如质因数分解法、短除法、辗转相除法(欧
几里得算法)等。
在实际应用中,这两个概念广泛应用于数学各个分支以及日常生活中,如分数化简、时间与
速度问题、工程设计等领域。
当然可以,以下分别给出求解两个整数最大公约数(GCD)和最小公倍数(LCM)的两种常
见方法:
1. **最大公约数(GCD)的求解方法:**
- **辗转相除法(欧几里得算法)**:
该方法基于一个数学原理:对于任何两个正整数 a 和 b(a>b),它们的最大公约数等于 a
除以 b 的余数 c 和 b 之间的最大公约数。
步骤如下:
a. 设定 a = b * q + r,其中 q 是 a 除以 b 的商,r 是余数。
b. 若 r=0,则 b 即为 a 与 b 的最大公约数;若 r≠0,则继续将 b 作为新的 a,r 作为新
的 b,重复步骤 a。
c. 直到 r=0 为止,此时的 b 就是最初 a 和 b 的最大公约数。
- **更相减损法**:
如果 a>b,则用 a-b,然后用得到的结果和原来的较小数再做同样处理,如此反复,直
到结果为 0,此时的较小数就是两数的最大公约数。但这种方法效率较低,一般不推荐在大
数情况下使用。
2. **最小公倍数(LCM)的求解方法:**
- **直接计算法**:
首先对两个数进行质因数分解,列出各自的质因数及其指数。然后取每个质因数中较
大的指数,最后将这些质因数按照原顺序并乘起来就得到了这两个数的最小公倍数。
例如,求 12 和 18 的最小公倍数:
12 = 2^2 * 3^1
18 = 2^1 * 3^2
所以,12 和 18 的最小公倍数为 2^2 * 3^2 = 36。
- **利用最大公约数关系法**: