我正在使用 Python v3.1 中的分数模块来计算最大公约数。我想知道使用什么算法。我在猜测欧几里德方法,但想确定一下。文档 ( http://docs.python.org/py3k/library/fractions.html?highlight=fractions.gcd#fractions.gcd ) 没有帮助。谁能给我线索?
最佳答案
根据 the 3.1.2 source code online ,这里是 Python-3.1.2/Lib/fractions.py
中定义的 gcd
:
def gcd(a, b):
"""Calculate the Greatest Common Divisor of a and b.
Unless b==0, the result will have the same sign as b (so that when
b is divided by it, the result comes out positive).
"""
while b:
a, b = b, a%b
return a
是的,它是用纯 Python 编写的欧几里得算法。
关于python - Python 在 fractions.gcd() 中使用什么算法?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2962640/