飞鱼博客

最大公约数（greatest common divisor，简写为gcd；或highest common factor，简写为hcf)，指某几个整数共有因子中最大的一个。
最小公倍数（Least Common Multiple，缩写lcm），指某几个整数公共倍数中最小的一个。

几个数学概念：

约数、倍数：如果数A能被数B整除（B不为零），A就叫做B的倍数，B就叫做A的约数（或因数、因子），倍数和约数是相互依存的。

公约数：几个数公有的约数叫做这几个数的公约数。一个数的约数的个数是有限的，其中最小的是1，最大的是它本身。例： 在2、4、6中，2就是2，4，6的最大公约数。

公倍数：几个数公有的倍数叫做这几个数的公倍数，其中最小的一个，叫做这几个数的最小公倍数。一个数的倍数是无限的，几个数的公倍数也是无限的。

质数：也称素数，指在一个大于1的自然数中，除了1和此整数自身外，没法被其他自然数整除的数。如：2、3、5、7、11……

质约数：也称质因数、质因子，既是约数又是质数的数。

分解质因数：一个大自然数，可以分解为多个质因数的相乘。方法从最小的质数开始分解。例如：12=2×6=2×2×3。

求最大公约数gcd：

欧几里得的辗转相除法：gcd(a,b)=gcd(b, a mod b)，其中"a mod b"是指"a ÷ b"的余数。该方法是在求两个较大数的gcd时，可以等效为求两个较小数的gcd，通过反复多次mod后，余数为零时，则最小的数（非零）即为gcd。
例如，求123456和7890的最大公约数：

最后最小的数为6，即123456和7890的最大公约数为6。

求最小公倍数lcm：

方法一：利用分解质因数的方法可以求出两个数的最小公倍数。
两个数一个称为大数，另一个称为小数，对两个数分别分解质因数，然后保留大数的所有质因数，再乘上小数中不重复的质因数，所得的积就为最小公倍数。
例1：求6和8的最小公倍数。
　6=2×3，8=2×2×2，
　保留8中的2×2×2，再乘上6中的3（2为重复的），
　所以6和8的最小公倍数是：(2×2×2)×3=24 。
例2：求12和8的最小公倍数。
　12=2×2×3，8=2×2×2，
　其中重复的为2×2，
　所以12和8的最小公倍数是：(2×2×3)×2=24。

方法二：先求gcd再求lcm。
最小公倍数等于两数之积除以最大公约数。
例：求12和8的最小公倍数。
　12和8的最大公约数为4，
　12×8÷4=24 ，
　所以两数的最小公倍数是24。