好资源导航 » 文章资讯 » Python实现的求解最大公约数算法示例

Python实现的求解最大公约数算法示例

2023-09-13 09:33:04 54

本文实例讲述了Python实现的求解最大公约数算法。分享给大家供大家参考，具体如下：

使用Python求解两个数的最大公约数的时候用到了前面介绍的分解质因式。其实，我写分解质因式程序的时候就是因为发现在实现最大公约数求解的过程中用到了这个功能。

比较令我开心的是之前学的一点Python集合处理功能居然在这个时候也派上了用场，小程序的完成让人感觉比较舒心。

代码实现如下：

#!/usr/bin/python
fromcollectionsimportCounter
defPrimeNum(num):
r_value=[]
foriinrange(2,num+1):
forjinrange(2,i):
ifi%j==0:
break
else:
r_value.append(i)
returnr_value
defPrimeFactorSolve(num,prime_list):
forninprime_list:
ifnum%n==0:
return[n,num/n]
defPrimeDivisor(num):
num_temp=num
prime_range=PrimeNum(num)
ret_value=[]
whilenumnotinprime_range:
factor_list=PrimeFactorSolve(num,prime_range)
ret_value.append(factor_list[0])
num=factor_list[1]
else:
ret_value.append(num)
returnCounter(ret_value)
defMaxDivisor(num1,num2):
dict1=PrimeDivisor(num1)
dict2=PrimeDivisor(num2)
max_divisor=1
forkey1indict1:
ifkey1indict2:
ifdict1[key1]
程序的执行结果如下：

E:\WorkSpace\01_编程语言\03_Python\math>pythonmax_divisor.py

6

1

1

8

9

通过验证，计算结果准确。
PS：这里再为大家推荐一款本站相关在线工具供大家参考：
在线最小公倍数/最大公约数计算工具：

http://tools.jb51.net/jisuanqi/gbs_gys_calc
更多关于Python相关内容感兴趣的读者可查看本站专题：《Python数学运算技巧总结》、《Python数据结构与算法教程》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》、《Python入门与进阶经典教程》及《Python文件与目录操作技巧汇总》
希望本文所述对大家Python程序设计有所帮助。

返回顶部
514930285
czq8825@qq.com

Python实现的求解最大公约数算法示例

热门推荐

随机推荐