记录python实现最大公约数&最小公位数两种算法

 

概念

最大公约数：指两个或多个整数共有约数中最大的一个

最小公倍数：两个或多个整数公有的倍数叫做它们的公倍数，其中除0以外最小的一个公倍数就叫做这几个整数的最小公倍数

二者关系：两个数之积=最小公倍数*最大公约数

 

实例

辗转相除法

 

a=int(input(\'please enter 1st num:\'))
b=int(input(\'please enter 2nd num:\'))
s=a*b
while a%b!=0:
    a,b=b,(a%b)   
else:
    print(b,\'is the maximum common divisor\')
    print(s//b,\'is the least common multiple\')

#运行结果
please enter 1st num:10
please enter 2nd num:15
5 is the Maximum common divisor
30 is the Least common multiple

 

 

更相减损法

a=int(input(\'please enter 1st num:\'))
b=int(input(\'please enter 2nd num:\'))
s=a*b
    
while a!=b:
    if a>b:
        a-=b
    elif a<b:
        b-=a
else:
    print(a,\'is the maximum common divisor\')
    print(s//a,\'is the least common multiple\')

#运行结果
please enter 1st num:40
please enter 2nd num:60
20 is the maximum common divisor
120 is the least common multiple

　　

辗转相除法与更相减损术的区别

（1）都是求最大公因数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。
（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到。

 

版权声明：本文为lilip原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/lilip/p/9316937.html