Python 最大公约数算法
以下代码用于实现最大公约数算法:
实例(Python 3.0+)
# Filename : test.py
# author by : www.runoob.com
# 定义一个函数
def hcf(x, y):
"""该函数返回两个数的最大公约数"""
# 获取最小值
if x > y:
smaller = y
else:
smaller = x
for i in range(1,smaller + 1):
if((x % i == 0) and (y % i == 0)):
hcf = i
return hcf
# 用户输入两个数字
num1 = int(input("输入第一个数字: "))
num2 = int(input("输入第二个数字: "))
print( num1,"和", num2,"的最大公约数为", hcf(num1, num2))
执行以上代码输出结果为:
输入第一个数字: 54 输入第二个数字: 24 54 和 24 的最大公约数为 6
HaydnLiao
Hay***iao@163.com
可按以下思路减少循环次数:
1. 当最小值为最大公约数时,直接返回;
2. 当最小值不为最大公约数时,最大公约数不会大于最小值的1/2;
3. 求最大公约数理应从大到小循环递减求最大。
实例:
HaydnLiao
Hay***iao@163.com
Joshua
cos***cosmos@163.com
参考方法:
Joshua
cos***cosmos@163.com
thinrock
thi***cker@gmail.com
参考方法:
thinrock
thi***cker@gmail.com
Santana
378***941@qq.com
从大到小一个一个计算:
Santana
378***941@qq.com
susion
245***1461@qq.com
两个数的最大公约数可以使用 欧几里得算法实现。即两个数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。
susion
245***1461@qq.com
黄桃果捞
zhe***ao@126.com
可以利用辗转相除的方法实现求两个正数的最大公约数,代码如下:
代码运行结果如下:
黄桃果捞
zhe***ao@126.com
桃之夭夭
956***900@qq.com
欧几得里算法的完善版,输入任意两个整数,求最大公约数。
桃之夭夭
956***900@qq.com
Egg_Hu
799***201@qq.com
不能再精简了吧
Egg_Hu
799***201@qq.com
The_Matrix
995***193@qq.com
求多个数的最大公约数
测试结果:
The_Matrix
995***193@qq.com
Alex
934***001@qq.com
使用 math 模块的 gcd()。
输出结果为:
Alex
934***001@qq.com
慕容君少
shu***hang89@126.com
参考方法:
慕容君少
shu***hang89@126.com
favourite45
jas***98862@163.com
用空列表方式实现最大公约数:
favourite45
jas***98862@163.com
白云黑土
mr.***gtao.sc@foxmail.com
求两个数的所有公约数:
白云黑土
mr.***gtao.sc@foxmail.com