Python编程算法【三十三】最大公约数

【案例内容】

求任意两个正整数的最大公约数(Greatest Common Divisor，GCD)。

【解题思路】

求解最大公约数可以使用欧几里德算法，也就是常说的辗转相除法。它是用较大的数（当被除数）去除较小的数（当除数）。若除得尽，则较小的数，即除数，就是这两个数的最大公约数。若除不尽，就先求出它们的余数，再拿刚才较小的数去除这个余数，反复操作直到除得尽为止，则此时的除数就是它们的最大公约数。
举例来说，要求20和12的最大公约数，先用较大的数20去除较小的数12，即20÷12，余数8；由于有余数，再用12÷8，余数4；继续用8÷4，此时除得尽，则4就是20和12的最大公约数。

【Python代码】

本题采用函数来处理，并且假设传入的第一个数比第二个数大，若除不尽再通过递归函数继续处理，直到除尽为止，整个过程会比较清晰、易懂。不用函数也行，小伙伴们可以自行尝试。