[已解决]新手一枚，今天做python17的动手题，有个最大公约数，没太看懂，谁可以帮我解释一下？

龙sir

def gcd(x, y):
    while y:
        t = x % y
        x = y
        y = t

    return x

最佳答案

月排行榜 / 总排行榜

kululu_love

2016-6-29 15:41:50

先用小的一个数除大的一个数,得第一个余数；
再用第一个余数除小的一个数,得第二个余数；
又用第二个余数除第一个余数,得第三个余数；
这样逐次用后一个数去除前一个余数,直到余数是0为止.那么,最后一个除数就是所求的最大公约数（如果最后的除数是1,那么原来的两个数是互质数）.
例如求1515和600的最大公约数,
第一次：用600除1515,商2余315；
第二次：用315除600,商1余285；
第三次：用285除315,商1余30；
第四次：用30除285,商9余15；
第五次：用15除30,商2余0.
1515和600的最大公约数是15.

跳转到最佳答案楼层

kululu_love

先用小的一个数除大的一个数,得第一个余数；
再用第一个余数除小的一个数,得第二个余数；
又用第二个余数除第一个余数,得第三个余数；
这样逐次用后一个数去除前一个余数,直到余数是0为止.那么,最后一个除数就是所求的最大公约数（如果最后的除数是1,那么原来的两个数是互质数）.
例如求1515和600的最大公约数,
第一次：用600除1515,商2余315；
第二次：用315除600,商1余285；
第三次：用285除315,商1余30；
第四次：用30除285,商9余15；
第五次：用15除30,商2余0.
1515和600的最大公约数是15.

wstxh

我才开始学习Python，但是没有足够的鱼币去看课后题，请问你们有没有小甲鱼的课后题啊

龙sir

kululu_love 发表于 2016-6-29 15:41
先用小的一个数除大的一个数,得第一个余数；
再用第一个余数除小的一个数,得第二个余数；
又用第二个余数 ...

谢谢啦，之前没明白为什么这样设计，原来最后都会变为较大的数对较小的数做取余，之后较小的数对得到的余数继续取余，直到余数为零是结束，输出那个最后的较小的数

龙sir

wstxh 发表于 2016-6-30 11:31
我才开始学习Python，但是没有足够的鱼币去看课后题，请问你们有没有小甲鱼的课后题啊

你可以签到，发帖，回帖......赚鱼币阿，我也是鱼币会感觉不够，反正坚持，鱼币会有的

龙sir

最大公约数：指两个或多个整数共有约数中最大的那个！
一开始这概念都忘了.....

wstxh

龙sir 发表于 2016-6-30 15:45
你可以签到，发帖，回帖......赚鱼币阿，我也是鱼币会感觉不够，反正坚持，鱼币会有的

我就是这样做的，只有慢慢的来啊

龙sir

wstxh 发表于 2016-6-30 16:34
我就是这样做的，只有慢慢的来啊

这些题很有意义，已经连续练习好多天了

wstxh

龙sir 发表于 2016-6-30 18:25
这些题很有意义，已经连续练习好多天了

嗯啦，就是啊，我也在练习。

龙sir

wstxh 发表于 2016-7-1 09:23
嗯啦，就是啊，我也在练习。

一起努力吧，少年