Python笔记：最大公约数算法与最小公倍数算法

忘是亡心i 2022-04-25 06:54 163阅读 0赞

### 文章目录 ###

*  求最大公约数
 *  求最小公倍数

**简介:**  
假设，如果数a能够被数b整除，a叫做b的倍数，b叫做a的约数。约数和倍数都表示一个整数和另一个整数的关系，不能单独存在。

*  几个整数中公有的约数，叫做这几个数的公约数；其中最大的一个，叫做这几个数的最大公约数。例如：12、16的公约数有1、2、4，其中最大的一个是4，4是12与16的最大公约数，一般记为（12，16）=4。12、15、18的最大公约数是3，记为（12，15，18）=3。
 *  几个自然数公有的倍数，叫做这几个数的公倍数，其中最小的一个自然数，叫做这几个数的最小公倍数。例如：4的倍数有4、8、12、16，……，6的倍数有6、12、18、24，……，4和6的公倍数有12、24，……，其中最小的是12，一般记为\[4，6\]=12。12、15、18的最小公倍数是180。记为\[12，15，18\]=180。若干个互质数的最小公倍数为它们的乘积的绝对值。

# 求最大公约数 #

# 定义一个函数
    def hcf(x, y):
       """该函数返回两个数的最大公约数"""
    
       # 获取最小值,由最小值来控制for循环次数
       if x > y:
           smaller = y
       else:
           smaller = x
    
       for i in range(1,smaller + 1):
           if((x % i == 0) and (y % i == 0)):#依次迭代1到最小值的数，然后让输入的最大值和最小值
                                             #除以其中每一个数，若同时能够除尽，则将迭代的数存放
                                             #到hcf变量中，当迭代到最后一个符合条件的i变量时,
                                             #hcf变量即存放最大的一个公约数了
               hcf = i
    
       return hcf
    
    
    # 用户输入两个数字
    num1 = int(input("输入第一个数字: "))
    num2 = int(input("输入第二个数字: "))
    
    print( num1,"和", num2,"的最大公约数为", hcf(num1, num2))

输出：

输入第一个数字: 12
    输入第二个数字: 16
    12 和 16 的最大公约数为 4

# 求最小公倍数 #

# 定义函数
    def lcm(x,y):
        #获取最大的数
        flag=1
        if x>y:
           greater = x
        else:
            greater = y
        while flag:#由最大值逐个自加1,若符合最小公倍数条件跳出循环
            if((greater%x==0) and (greater%y==0)):
                lcm=greater
                flag=0
            greater+=1
        return lcm
    # 获取用户输入
    num1 = int(input("请输入第一个数字："))
    num2 = int(input("请输入第二个数字："))
    print(num1,"和",num2,"的最小公倍数为",lcm(num1,num2))

输出:

输入第一个数字: 4
    输入第二个数字: 6
    4 和 6 的最小公倍数为 12