找出两个数的最大公因数?这里有两种超简单情况!


要找出两个数的最大公因数(GCD),有两种非常简单的方法:

1. 列举法:找出两个数的所有因数,然后从中找出最大的那个公因数。

- 例如,要找12和18的最大公因数:

- 12的因数有:1, 2, 3, 4, 6, 12

- 18的因数有:1, 2, 3, 6, 9, 18

- 公因数有:1, 2, 3, 6

- 最大公因数是6。

2. 欧几里得算法:这是一种更高效的算法,通过连续的减法或除法来找到最大公因数。

- 例如,要找12和18的最大公因数:

- 用较大的数除以较小的数,得到余数:18 ÷ 12 = 1 余 6

- 然后用较小的数(12)和余数(6)继续这个过程:12 ÷ 6 = 2 余 0

- 当余数为0时,最后一个非零余数就是最大公因数,即6。

这两种方法都非常简单,列举法适合小数,而欧几里得算法适合较大数。