求最大公约数,和最小公倍数的规则?
最大公约数(Greatest Common Divisor,简称GCD)是指两个或多个整数共有约数中最大的一个。例如,12和18的最大公约数是6,因为12和18同时都能被6整除。
求最大公约数的规则包括:
辗转相除法:假设有两个整数a和b,求它们的最大公约数。首先,用a除以b,得到余数r1,然后用b除以r1,得到余数r2,继续用r1除以r2,得到余数r3,以此类推,直到余数为0。此时,最大公约数就是最后一个非零余数。
更相减损法:假设有两个整数a和b,求它们的最大公约数。首先,用较大的数减去较小的数,得到差d,然后用较小的数和d继续做同样的操作,直到两个数相等。此时,最大公约数就是这两个数的值。
最小公倍数(Least Common Multiple,简称LCM)是指两个或多个整数公有的倍数中最小的一个。例如,12和18的最小公倍数是36,因为12的倍数是12、24、36,18的倍数是18、36,而它们共有的倍数中最小的一个是36。
求最小公倍数的规则包括:
分解质因数法:将两个数分别分解成质因数的乘积,然后取它们的公共质因数和非公共质因数的乘积,即为它们的最小公倍数。
最大公约数法:假设有两个整数a和b,它们的最大公约数为gcd,最小公倍数为lcm。则有lcm = a * b / gcd。
以上是求最大公约数和最小公倍数的规则,可以根据实际情况选择适合的方法进行计算。