小评论
上次我们介绍了一种求最大公约数的特殊方法，叫做除法。你还记得吗？
欧几里得算法
将较大的数除以较小的数，然后将除数除以出现的余数(第一个余数)，然后将第一个余数除以出现的余数(第二个余数)，并重复此操作，直到最后一个余数为0。如果要求两个数的最大公约数，那么最终的除数就是这两个数的最大公约数。
所以，今天我们就来总结一下求最大公约数的方法。
求最大公约数方法综述
1.素因子分解方法
思维:将每个数分解成素因子，然后提取每个数中所有的公共素因子相乘，得到的乘积就是这些数的最大公约数。
例如，假设我们找到24和60的最大公约数。
第一步:分解24和60。
24=2X2X2X3
60=2X3X2X5
第二步:24和60的最大公约数= 24和60共享的公因数相乘，即2X2X3=12。
2.短除法
思考:用短除法求最大公约数，首先连续去掉这些数的公约数，直到所有商数互为素数，然后将所有除数相乘，得到的乘积就是这些数的最大公约数。
短除法的本质是素因子分解法，但素因子分解是用短除法符号进行的。
示例:
12的因子是:1，2，3，4，6，12。
18的因子是:1，2，3，6，9，18。
12和18的公因数是:1，2，3，6。
12和18之间最大的公因数是6。
3、多相损耗法
思考:
第一步:任意给两个正整数；确定是否都是偶数。如果是，用2减；如果没有，执行第二步。
第二步:将较小的数减去较大的数，然后将差值与较小的数进行比较，再将该数减去较大的数。继续此操作，直到产生的减数和差值相等。
那么第一步中的一些2和第二步中的相等数的乘积就是最大公约数。
示例:
用多失相法求98和63的最大公约数。
因为63不是偶数，所以将98和63减一个大的数并减去它们:
98-63=35
63-35=28
35-28=7
28-7=21
21-7=14
14-7=7
所以98和63的最大公约数等于7。
代码实现:
4.转身分开
捻转除法和除法在前一篇文章中有详细介绍。
欧几里得算法
你掌握了多少种方法~
1.《求最大公约数 最大公约数求法大全》援引自互联网，旨在传递更多网络信息知识，仅代表作者本人观点，与本网站无关，侵删请联系页脚下方联系方式。
2.《求最大公约数 最大公约数求法大全》仅供读者参考，本网站未对该内容进行证实，对其原创性、真实性、完整性、及时性不作任何保证。
3.文章转载时请保留本站内容来源地址，https://www.lu-xu.com/shehui/648231.html
