[已解决]利用欧几里得算法（脑补链接）求最大公约数

枫枫duck

def gcd(x,y):
    big = x if x>y else y
    small = y if x>y else x
    while 1:
        num = big%small 
        if num == 0:
            return small
            break
        else:
            big = small
            small = big%small [code]
       
以上是我的编码，它会报错
[code]gcd(4,6)
Traceback (most recent call last):
  File "<pyshell#0>", line 1, in <module>
    gcd(4,6)
  File "C:\Users\15860\Desktop\python学习\lesson17函数\欧几里得.py", line 5, in gcd
    num = big%small
ZeroDivisionError: integer division or modulo by zero

是说除数不能为0吗，为什么错了呢

最佳答案

月排行榜 / 总排行榜

liuzhengyuan

2020-4-9 10:38:51

这个不对。。。
你这个

else:
            big = small
            small = big%small 

想一想，
你先把big赋值small
这样big和small就一样了
两个一样的数相除余数就是0

跳转到最佳答案楼层

liuzhengyuan

这个不对。。。
你这个

else:
            big = small
            small = big%small 

想一想，
你先把big赋值small
这样big和small就一样了
两个一样的数相除余数就是0

qiuyouzhi

def gcd(x,y):
    big = x if x>y else y
    small = y if x>y else x
    while 1:
        num = big % small
        if num == 0:
            return small
        else:
            small = big%small

print(gcd(4,6))

return了之后，程序就直接结束了，不用break

枫枫duck

liuzhengyuan 发表于 2020-4-9 10:38
这个不对。。。

你这个

我这里是想把small的值赋给big来达到
"""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"""
这种效果

qiuyouzhi

liuzhengyuan 发表于 2020-4-9 10:38
这个不对。。。

你这个

为什么要big == small呢？
直接删掉不行？

枫枫duck

qiuyouzhi 发表于 2020-4-9 10:39
return了之后，程序就直接结束了，不用break

谢谢提醒，但不影响程序是错的呀...

枫枫duck

liuzhengyuan 发表于 2020-4-9 10:38
这个不对。。。

你这个

我知道你的意思了，big已经改变了

qiuyouzhi

枫枫duck 发表于 2020-4-9 10:41
我这里是想把small的值赋给big来达到
"""1997 / 615 = 3 (余 152)
615 / 152 = 4(余7)

假设按你的来：
1997 / 615 余 152
然后big = small，也就是把1997改成615
这时就变成615/615了

枫枫duck

qiuyouzhi 发表于 2020-4-9 10:45
假设按你的来：
1997 / 615 余 152
然后big = small，也就是把1997改成615

我把它修改了，应该没问题了！让small=num就好了

def gcd(x,y):
    big = x if x>y else y
    small = y if x>y else x
    while 1:
        num = big%small 
        if num == 0:
            return small            
        else:
            big = small
            small = num