欧几里得算法(脑补链接)求最大公约数(Python)
2023-03-20 14:59:58 时间
欧几里得算法又称辗转相除法,是指用于计算两个非负整数a,b的最大公约数。
假如需要求 1997 和 615 两个正整数的最大公约数,用欧几里得算法,是这样进行的:
1997 / 615 = 3 (余 152)
615 / 152 = 4(余7)
152 / 7 = 21(余5)
7 / 5 = 1 (余2)
5 / 2 = 2 (余1)
2 / 1 = 2 (余0)
至此,最大公约数为1
简单来说就是用大数除小数,然后接着将每个式子里面的除数不断除以余数直到余数为零,那么最后的除数便是公约数。
代码:
def gcd(x, y):
dividend = max(x,y)#被除数
divider = min(x,y)#除数
remainder = dividend % divider#余数
while True:
if remainder == 0:
break
dividend = divider
divider = remainder
remainder = dividend % divider
return divider
相关文章
- 在 Kubernetes 上运行 Pgpool-Il 实现 PostgreSQL 查询(读)负载均衡和连接池
- QQ PC版9.4.2更新:新增AI降噪 语音、视频通话更清晰
- Typescript代码整洁之道
- 2021年Web开发的7大趋势
- GitHub发布2020年度报告:开发者数量超5600万
- 面试官:关于Spring就问这13个
- 电脑狂、理论家、情报员……你是哪种类型的软件工程师?
- Socket粘包问题的3种解决方案,哪一种更优秀!
- 实践: Jenkins Core Api & Job DSL创建项目
- 5分钟带你快速了解ServiceMesh的前世今生
- 学习算法必备:时间复杂度与空间复杂度,你了解多少
- Zookeeper和Eureka有哪些区别?
- Try..Catch 不能捕获的错误有哪些?注意事项又有哪些?
- 搭建Sonarqube 代码质量扫描环境
- 如何实现 ASP.NET Core WebApi 的版本化
- 这样调优:让你的 IDEA 快到飞起来,效率真高!
- 机器编程驾到,会让2700万程序员丢掉饭碗吗?
- 偷师 Next.js:我学到的 6 个设计技巧
- 关于动态规划,你该了解这些!
- 真正影响DevOps/DevSecOps应用的趋势是什么?