欧几里得－辗转相除法

Tetraodontidae

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

    return x
   
print(gcd(4, 6))

请问能帮忙解释下为什么  x = y  y = t 和返回x  
谢谢

和vvv

比如输入4和6，则
x=4,y=6
余数t=x%y=4%6=4
现在x=y=6,y=t=4,y=t=4不等于零，继续循环
t=x%y=6%4=2,
x=y=4,y=t=2,还不为零，继续循环
t=x%y=4%2=0
x=y=2,
y=t=0,循环结束。
return x，因x=y=2.
故返回结果2，即4和6的最大公约数为2

bhsx

谢谢你让我多学了个算法,

相关原理
两个整数的最大公约数是能够同时整除它们的最大的正整数。
辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数的相除余数的最大公约数。
例如，252和105的最大公约数是21(252 = 21 × 12；105 = 21 × 5);
因为252 ÷105 = 2......42，所以(105,42)是21。在这个过程中，较大的数缩小了，所以继续进行同样的计算可以不断缩小这两个数直至余数变为零。这时的除数就是所求的两个数的最大公约数。由辗转相除法也可以推出，两数的最大公约数可以用两数的整数倍相加来表示，如21 = 5 × 105 + （−2） × 252。这个重要的等式叫做贝祖等式（又称“裴蜀定理”）。

back0893

这个算法为何不百度

Tetraodontidae

和vvv 发表于 2016-6-24 18:18
比如输入4和6，则
x=4,y=6
余数t=x%y=4%6=4

谢谢

四十二

学到了……

感觉其实实现的东西并不复杂，加上名字逼格爆表……

七度

看不懂呢，我感觉有点复杂，高中学得早忘记了

哪吒三太子

谢谢分享