首页 > 代码库 > python 最大公约数

python 最大公约数

2024-08-24 04:09:09   217人阅读

求解两个整数（不能是负数）的最大公约数（要求两数不能同时为0）

当两数都是0时，最大公约数为0

方式一：穷举法
技术分享 
 1 def GCU(m, n):
 2     if not m:
 3         return n
 4     elif not n:
 5         return m
 6     elif m is n:
 7         return m
 8 
 9     if m > n:
10         gcd = n
11     else:
12         gcd = m
13 
14     while m%gcd or n%gcd:
15         gcd -= 1
16 
17     return gcd
View Code

方式二：相减法

技术分享 
 1 def GCU(m, n):
 2     if not m:
 3         return n
 4     elif not n:
 5         return m
 6     elif m is n:
 7         return m
 8 
 9     while m!=n:
10         if m>n:
11             m -= n
12         else:
13             n -= m
14 
15     return m
View Code

方式三：欧几里德辗转相除法

技术分享 
 1 def GCU(m, n):
 2     if not m:
 3         return n
 4     elif not n:
 5         return m
 6     elif m is n:
 7         return m
 8 
 9     while m%n:
10         m, n = n, m%n
11 
12     return n
View Code

方式四：欧几里德辗转相除法 递归实现

技术分享 
 1 def GCU(m,n):
 2     if not n:
 3         return m
 4     else:
 5         return GCU(n, m%n)
 6 
 7 if __name__ == ‘__main__‘:
 8     a = int(input(‘Please input the first integers : ‘))
 9     b = int(input(‘Please input the second integers : ‘))
10     result = GCU(a, b)
11     print(‘GCU = ‘, result)
View Code

 

python 最大公约数


联系
我们