最大公约数怎么求算法
网上买衣服尺码表-融资租赁行业
2023年3月17日发(作者：电抗器的作用及原理).
、查找约数法．
先分别找出每个数的所有约数，再从两个数的约数中找出公有的约数，其中最大的一个就是
最大公约数．
例如，求和的最大公约数．
的约数有：、、、、、；
的约数有：、、、、、、、．
和的公约数有：、、、，其中就是和的最大公约数．
更相减损术
《九章算术》是中国古代的数学专著，其中的“更相减损术”可以用来求
两个数的最大公约数，即“可半者半之，不可半者，副置分母、子之数，
以少减多，更相减损，求其等也。以等数约之。”
翻译成现代语言如下：
第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用
约简；若不是则执行第二步。
第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，
并以大数减小数。继续这个操作，直到所得的减数和差相等为止。
则第一步中约掉的若干个与第二步中等数的乘积就是所求的最大公约
数。
其中所说的“等数”，就是最大公约数。求“等数”的办法是“更相
减损”法。
、辗转相除法．
当两个数都较大时，采用辗转相除法比较方便．其方法是：
以小数除大数，如果能整除，那么小数就是所求的最大公约数．否则就用余数来除刚才
的除数；再用这新除法的余数去除刚才的余数．依此类推，直到一个除法能够整除，这时作
为除数的数就是所求的最大公约数．
例如：求和的最大公约数时，可作如下除法．
÷＝余
÷＝余
÷＝余
÷＝余
÷＝余
÷＝
于是得知，和的最大公约数是．
辗转相除法适用比较广，比短除法要好得多，它能保证求出任意两个数的最大公约数．
、求差判定法．
如果两个数相差不大，可以用大数减去小数，所得的差与小数的最大公约数就是原来两
个数的最大公约数．例如：求和的最大公约数．－＝，和的最大公约数是，所以和的最大公
约数是．
如果两个数相差较大，可以用大数减去小数的若干倍，一直减到差比小数小为止，差和小数
的最大公约数就是原来两数的最大公约数．例如：求和的最大公约数．－＝，－＝，－＝，
－＝，－＝，和的最大公约数是，所以和的最大公约数就是．
、分解因式法．
先分别把两个数分解质因数，再找出它们全部公有的质因数，然后把这些公有质因数相
乘，得到的积就是这两个数的最大公约数．
例如：求和的最大公约数．因为＝××，＝××××，所以和的最大公约数是×＝．
、短除法．
为了简便，将两个数的分解过程用同一个短除法来表示，那么最大公约数就是所有除数
的乘积．
例如：求和的最大公约数．
因为：
和互质，所以和的最大公约数是×＝．
、除法法．
当两个数中较小的数是质数时，可采用除法求解．即用较大的数除以较小的数，如果能
够整除，则较小的数是这两个数的最大公约数．
例如：求和，和的最大公约数．因为÷＝，÷＝．（和都是质数．）所以和的最大公约
数是，和的最大公约数是．
、缩倍法．