《九章算术》是中国古代的数学专著，其中的“更相减损术”可以用来求两个数的最大公约数，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。”

# -*- coding:utf-8 -*-
#! python2
def MaxCommDivisor(m,n):
# even process
while m % 2 == 0 and n % 2 == 0:
m = m / 2
n = n / 2
# exchange order when needed
if m < n:
m,n = n,m
# calculate the max comm divisor
while m - n != n:
diff = m - n
if diff > n:
m = diff
else:
m = n
n = diff
return n
print(MaxCommDivisor(55,120))
print(MaxCommDivisor(55,77))
print(MaxCommDivisor(32,64))
print(MaxCommDivisor(16,128))

def MaxCommDivisor(m,n):
com_factor = 1
if m == n:
return n
else:
# process for even number
while m % 2 == 0 and n % 2 == 0:
m = int(m / 2)
n = int(n / 2)
com_factor *= 2
if m < n:
m,n = n,m
diff = m - n
while n != diff:
m = diff
if m < n:
m,n = n,m
diff = m - n
return n * com_factor
print(MaxCommDivisor(55,120))
print(MaxCommDivisor(55,77))
print(MaxCommDivisor(32,64))
print(MaxCommDivisor(16,128))

PS：这里再为大家推荐几款计算工具供大家进一步参考借鉴：

http://tools.jb51.net/jisuanqi/equ_jisuanqi

http://tools.jb51.net/jisuanqi/jsqkexue

http://tools.jb51.net/jisuanqi/jsq

tags: Python,MaxCommDivisor,最大公约数,diff,求解,print,算法,相减,损术,while,jisuanqi,示例

1.凡CodeSecTeam转载的文章,均出自其它媒体或其他官网介绍,目的在于传递更多的信息,并不代表本站赞同其观点和其真实性负责；
2.转载的文章仅代表原创作者观点,与本站无关。其原创性以及文中陈述文字和内容未经本站证实,本站对该文以及其中全部或者部分内容、文字的真实性、完整性、及时性，不作出任何保证或承若；
3.如本站转载稿涉及版权等问题,请作者及时联系本站,我们会及时处理。