1.欧几里得算法：
欧几里得算法又称辗转相除法，是求两个整数的最大公约数非常有效的算法，具体内容是：两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。
2.欧几里得算法证明 ：
a可以表示成a = kb + r（a，b，k，r皆为正整数，且r < b），则r = a mod b。
假设d是a，b的一个公约数，记作d|a，d|b，即a和b都可以被d整除。而r = a - kb，两边同时除以d，r/d=a/d-kb/d=m，由等式右边可知m为整数，因此d|r。因此d也是b，a mod b的公约数。
假设d是b,a mod b的公约数, 则d|b，d|(a - k * b)，k是一个整数。进而d|a，因此d也是a，b的公约数因此(a，b)和(b，a mod b)的公约数是一样的，其最大公约数也必然相等，得证。
3.欧几里得算法python实现：
使用递归方法实现，当较小整数为0时，则表明上一次相除已除尽，所以上一次相除时的除数（当次输入gcd函数的较大数）是最大公约数。当较小整数不为0时，则继续递归调用gcd函数。
def gcd(a, b):
if a < b:
a, b = b, a
return a if b == 0 else gcd(b, a % b)if __name__ == "__main__":
print(gcd(8, 16))
print(gcd(8251, 6105))【欧几里得算法证明及python实现】
推荐阅读
- 人工智能|干货！人体姿态估计与运动预测
- 分析COMP122 The Caesar Cipher
- 技术|为参加2021年蓝桥杯Java软件开发大学B组细心整理常见基础知识、搜索和常用算法解析例题（持续更新...)
- C语言学习(bit)|16.C语言进阶——深度剖析数据在内存中的存储
- Python机器学习基础与进阶|Python机器学习--集成学习算法--XGBoost算法
- 数据结构与算法|【算法】力扣第 266场周赛
- 数据结构和算法|LeetCode 的正确使用方式
- leetcode|今天开始记录自己的力扣之路
- 人工智能|【机器学习】深度盘点（详细介绍 Python 中的 7 种交叉验证方法！）
- 网络|简单聊聊压缩网络