教你快速找两个整数的最大公约数的方法

要找到两个整数的最大公约数（GCD），我们可以使用一种非常有效且古老的方法，称为欧几里得算法。这个方法基于一个重要的数学定理：两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。具体步骤如下：

首先，假设我们有两个整数a和b，其中a > b。我们用a除以b，得到商q和余数r，即a = bq + r。如果余数r不为0，我们继续用b除以r，得到新的商和余数，直到余数为0。当余数为0时，最后一个非零余数就是a和b的最大公约数。

例如，要找到28和36的最大公约数，我们首先用36除以28，得到商1和余数8，即36 = 28 1 + 8。然后，用28除以8，得到商3和余数4，即28 = 8 3 + 4。接着，用8除以4，得到商2和余数0，即8 = 4 2 + 0。当余数为0时，最后一个非零余数是4，所以28和36的最大公约数是4。

欧几里得算法非常高效，尤其是对于大整数，它比其他方法（如列举所有因数）要快得多。这个方法不仅简单，而且应用广泛，是数学和计算机科学中的重要工具。