简介：求两个数的最大公约数的四种解法，推荐欧几里得算法。

1、枚举法：

将两数x，y中最小的放到smaller中
用x，y分别对 i（1到smaller之间）求余数，看是否能被整除
直到x，y同时被i整除
如不能整除，i+1后继续，直到i等于smaller

2、欧几里得算法：
该方法其实就是辗转相除法的递归版本实现
如果 x = 0，返回 x；判断 x > y
如果 x > y，则x、y的最大公约数等于 y 与 x % y 的最大公约数，以此递归

3、辗转相减法：

如果x > y ，x = x - y
如果y > x ，y = y - x
假如x = y ，则 x 或 y 是最大公约数
如果x != y,则继续继续相减，直至x = y

4、辗转相除法：

两数求余temp = x % y
temp = 0 时，y为最大公约数
temp != 0 时，x = y；y = temp 注：该循环的是否继续的判断条件就是temp是否为0

源码：

# -*- coding: utf-8 -*-
# time: 2022/5/29 19:39
# file: common_divisor.py
# 公众号: 玩转测试开发


def enumerate_number(x, y):
    """
    枚举法：
    将两数x，y中最小的放到smaller中
    用x，y分别对 i（1到smaller之间）求余数，看是否能被整除
    直到x，y同时被i整除
    如不能整除，i+1后继续，直到i等于smaller
    """
    smaller = y if x > y else x

    # for i in range(1, smaller + 1):
    #     if (x % i == 0) and (y % i == 0):
    #         result = i

    result = [i for i in range(1, smaller + 1) if (x % i == 0) and (y % i == 0)]

    return result[-1]


def euclidean_algorithm(x, y):
    """
    欧几里得算法：
    该方法其实就是辗转相除法的递归版本实现
    如果 x = 0，返回 x；判断 x > y
    如果 x > y，则x、y的最大公约数等于 y 与 x % y 的最大公约数，以此递归
    """
    if y == 0:
        return x
    return euclidean_algorithm(y, x % y)


def tossing_subtracting(x, y):
    """
    辗转相减法：
    如果x > y ，x = x - y
    如果y > x ，y = y - x
    假如x = y ，则 x 或 y 是最大公约数
    如果x != y,则继续继续相减，直至x = y
    """
    while x != y:
        if x > y:
            x = x - y
        else:
            y = y - x
    return x


def tossing_dividing(x, y):
    """
    辗转相除法：
    两数求余temp = x % y
    temp = 0 时，y为最大公约数
    temp != 0 时，x = y；y = temp 注：该循环的是否继续的判断条件就是temp是否为0
    """
    temp = x % y
    while temp != 0:
        x = y
        y = temp
        temp = x % y
    return y


if __name__ == '__main__':
    r1 = enumerate_number(15, 25)
    r2 = euclidean_algorithm(15, 25)
    r3 = tossing_subtracting(15, 25)
    r4 = tossing_dividing(15, 25)
    print(r1)
    print(r2)
    print(r3)
    print(r4)

微信公众号：玩转测试开发
欢迎关注，共同进步，谢谢！