最大公约数

gzj137070928

计算两个数的最大公约数

1. def gcd(x, y):
   
2.     '''该函数返回两个数的最大公约数'''
   
3.     if not(x > 0 and y > 0):
   
4.         print("Invalid numbers!")
   
5.     # 用匿名函数简化构造取较小值的函数
   
6.     smaller = lambda x,y: x if x < y else y
   
7.     for i in range(1, smaller(x, y) + 1):
   
8.         if (x % i == 0) and (y % i == 0):
   
9.             gcd = i
   
10.     return gcd
    
11. 
    
12. 
    
13. num1 = int(input('请输入第一个数字：'))
    
14. num2 = int(input('请输入第二个数字：'))
    
15. print(num1, '和', num2, '的最大公约数是：', gcd(num1, num2))

复制代码

嘉岳呀

我上周六刚学的最大公约数和最小公倍数

gzj137070928

嘉岳呀 发表于 2020-10-14 18:39
我上周六刚学的最大公约数和最小公倍数

还有简洁版：利用欧几里得算法
思想简介：(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等

1. def gcd2(x, y):
   
2.     while y:
   
3.         t = x % y
   
4.         x = y
   
5.         y = t
   
6.     return x
   
7. 
   
8. 
   
9. print(gcd2(4, 6))

复制代码