# 使用递归求两正整数的最大公因数
def gcd(a, b):
# 当入参其中至少有一个不为正整数时抛出异常
if a <= 0 or b <= 0:
raise Exception("Illegal Argument Exception!", a, b)
# 当数相等时最大公因数为任意一个数
if a == b:
return a
# 逻辑与运算判断是否为奇数
if a & 1:
if b & 1:
return a > b and gcd(a - b, b) or gcd(b - a, a)
# 一奇一偶时，对偶数进行位运算 >>1等价于b/2
return gcd(a, b >> 1)
if b & 1:
return gcd(a >> 1, b)
# 当两偶时，同时进行位运算>>1，相当于提取公因数2
# 然后进行位运算<<1 对结果乘以2的得到公因数
return gcd(a >> 1, b >> 1) << 1
最大公因数
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
