求最大公约数 最大公约数求法大全

小评论

上次我们介绍了一种求最大公约数的特殊方法，叫做除法。你还记得吗？

欧几里得算法

将较大的数除以较小的数，然后将除数除以出现的余数(第一个余数)，然后将第一个余数除以出现的余数(第二个余数)，并重复此操作，直到最后一个余数为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.转身分开

捻转除法和除法在前一篇文章中有详细介绍。

欧几里得算法

你掌握了多少种方法~