一.思路分析

因为之前接触过这个问题，所以自己是知道欧几里得算法和穷举法计算最大公约数，在求出两个数的最大公约数之后，便可以利用lcm(a,b) = (a*b)/gcd(a,b) 计算出两个数的最小公倍数。之后还上网查了一下stein算法，最后在理解stein算法的基础上解决了这个问题。下面我会一一对这几种算法进行分析：

1.欧几里得法(辗转相除法)

这条算法基于一个定理：两个正整数a和b（a>b），它们的最大公约数等于a除以b的余数c和b之间的最大公约数。比如10和25，25除以10商2余5，那么10和25的最大公约数，等同于10和5的最大公约数。

基于这条定理：

首先，我们先计算出a除以b的余数c，把问题转化成求出b和c的最大公约数；然后计算出b除以c的余数d，把问题转化成求出c和d的最大公约数；再然后计算出c除以d的余数e，把问题转化成求出d和e的最大公约数……以此类推，逐渐把两个较大整数之间的运算简化成两个较小整数之间的运算，直到两个数可以整除，或者其中一个数减小到1为止。贴代码：

# -*- coding:utf-8 -*- 
# @Author: Jiawei Han

def first_way(a, b):
    """
    第一种方法：欧几里得算法----辗转相除法
    :param a: 第一个数
    :param b: 第二个数
    :return: 最大公约数
    """
    # 如果最终余数为0 公约数就计算出来了
    while(b!=0):
        temp = a % b
        a = b
        b = temp
    return a

2.穷举法(一个一个除)

这个比较好理解。因为a,b两个数的最大公因数肯定小于等于相对更小的那个数，所以从两个数中较小数开始由大到小列举，直到找到公约数立即中断列举，得到的公约数便是最大公约数。代码如下：

def second_way(a, b):
    """
    第二种方法：一个一个除
    :param a: 第一个数
    :param b: 第二个数
    :return: 最大公约数
    """
    # 保证a>b
    if(a<b):
        a,b = b,a
    for i in range(1,b+1):
        if (a%i==0) and (b%i==0):
            value = i;
    return value

3.stein算法

看下面这两个结论

gcd(a, a) = a，也就是一个数和他自己的公约数是其自身。

gcd(ka, kb) = k * gcd(a, b)，也就是最大公约数运算和倍乘运算可以交换，特殊的，当k=2时，说明两个偶数的最大公约数比如能被2整除。

def third_way(a,b):
    """
    第三种方法思想：stein算法
        gcd(a,a)=a，也就是一个数和其自身的公约数仍是其自身。
        gcd(ka,kb)=k gcd(a,b)，也就是最大公约数运算和倍乘运算可以交换。特殊地，当k=2时，说明两个偶数的最大公约数必然能被2整除。
        当k与b互为质数，gcd(ka,b)=gcd(a,b)，也就是约掉两个数中只有其中一个含有的因子不影响最大公约数。特殊地，当k=2时，说明计算一个偶数
    和一个奇数的最大公约数时，可以先将偶数除以2。
    :param a: 第一个数
    :param b: 第二个数
    :return: 最大公约数
    """
    #保证b比a小
    if a < b:
        a, b = b, a

    if (0 == b):
        return a
    # a,b都是偶数 除2右移一位即可
    if a % 2 == 0 and b % 2 == 0:
        return 2 * third_way(a >> 1, b >> 1)
    # a是偶数
    if a % 2 == 0:
        return third_way(a >> 1, b)
    # b是偶数
    if b % 2 == 0:
        return third_way(a, b >> 1)
    # 都是奇数
    return third_way((a + b) >> 1, (a - b) >> 1)

求出a,b的最大公约数后，利用lcm(a,b) = (a*b)/gcd(a,b) 计算出两个数的最小公倍数：

# 求两个数的最小公倍数
def lcm(a,b):
    return a * b / third_way(a, b)

二.提高要求

计算三个数的最大公约数时，我是利用之前写好的计算2个数的最大公约数的方法，先算出a,b的公约数，再用a,b的公约数与c再代入方法，此时返回的值就是三个数的最大公约数了。

同样，在计算三个数的最小公倍数时，多次嵌套，先求出两个数的最小公倍数，再求其与第三个数的最小公倍数。

def three_num(a,b,c):
    """
    求三个数的最大公约数
    :param a: 第一个数
    :param b: 第二个数
    :param c: 第三个数
    :return: 这三个数的最大公约数
    """
    # 多次嵌套，返回3个数的最大公约数
    return first_way(first_way(a,b),c)

a,b,c =map(int,input("请输入需要计算的整数用空格隔开：").split())
        print("这三个数的最大公约数是：" + str(three_num(a,b,c)))
        # 我这里使用多次嵌套，先求出两个数的，再求与第三个数的最小公倍数
        print("这三个数的最小公倍数是：" + str(lcm(a,b)*c/third_way(third_way(a,b),c)))

main方法：

if __name__ == '__main__':
    flag = input("请选择功能：\n   1.计算两个数的最大公约数和最小公倍数\n   2.计算三个数的最大公约数和最小公倍数\n")
    if flag=='1':
        a,b = map(int,input("请输入需要计算的整数用空格隔开：").split())
        print("这两个数的最大公约数为" + str(third_way(a, b)))
        val = lcm(a, b)
        # 利用最大公约数求最小公倍数
        print("最小公倍数为：" + str(val))
    elif flag=='2':
        a,b,c =map(int,input("请输入需要计算的整数用空格隔开：").split())
        print("这三个数的最大公约数是：" + str(three_num(a,b,c)))
        # 我这里使用多次嵌套，先求出两个数的，再求与第三个数的最小公倍数
        print("这三个数的最小公倍数是：" + str(lcm(a,b)*c/third_way(third_way(a,b),c)))
    else:
        print("请输入正确序号")

三.测试截图

求两个数的：

求三个数的：

原文链接：https://blog.csdn.net/J0Han/article/details/82467335