Skip to content

Instantly share code, notes, and snippets.

@RagtagGeoduck
Last active February 20, 2021 03:33
Show Gist options
  • Save RagtagGeoduck/352fb3903fc23dc613b11b5660f6936f to your computer and use it in GitHub Desktop.
Save RagtagGeoduck/352fb3903fc23dc613b11b5660f6936f to your computer and use it in GitHub Desktop.
[欧几里得算法] #Python #算法
def gcd(m, n):
if n == 0:
m, n = n, m
while m != 0:
m, n = n%m, m
return n
"""
最著名的寻找最大公因数的方法是欧几里得算法.
欧几里得算法规定:
对于两个整数 m 和 n,如果 n 能整除 m,那么就将 n 除以 m 的结果作为新的 n,
如果 n 不能再整除 m,那么最大公因数就是 n 或者 m 被 n 整除的余数。
注意这个最大公因数的算法只适用于分母是正数的情况。
因为我们可以把负分数的负号归结于分子,所以这种算法还是比较实用的。
"""
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment