欧几里得算法+Python代码

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了欧几里得算法+Python代码，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含371字，纯文字阅读大概需要1分钟。

内容图文

算法原理

对于a = b*q + c
存在(a,b) = (b,c)

证明：
令d = (a,b)
有d|a, d|b
由c = a - b*q
知d|c,即d是b,c的公因数

令e = (b,c)
显然有d<=e
而e|b, e|c
由a = b*q + c
知e|a,即e是a,b的公因数
可得d>=e

d=e,即(a,b) = (b,c)

Python代码

# encoding:utf-8


def myGCD(a, b):
    """
    a,b顺序无所谓
    """
    while b != 0:
        # print(a, b)
        a, b = b, a % b
    return a


# print(myGCD(12075, 4655))
print(myGCD(172, 46))

内容总结

以上是互联网集市为您收集整理的欧几里得算法+Python代码全部内容，希望文章能够帮你解决欧几里得算法+Python代码所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---