枚举算法虽然比较简单，但是效率不高，下面再介绍一种求最大公约数的方法。
辗转相除法， 又名欧几里德算法（Euclidean algorithm），是求最大公约数的一种方法。它的具体做法是：用较大数除以较小数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。
（78,14）
78除以14余8
14除以8 余6
8除以6 余2
6除以2 余0
2即为78和14的最大公约数4步得出答案。
Python 求解
''' 求两个数最大公约数 辗转相除法 gcd（a,b) = gcd(b,a%b) ''' def gcd(a, b): if a % b == 0: # 如果a除以b余数为0 return b # 返回b的值就是a和b的最大公约数 return gcd(b, a % b) # 否则递归调用 if __name__ == '__main__': print(gcd(78, 14)) # 求78和14 最大公约数
0 评论 最近
没有评论！