Python中的欧几里得算法

Question

嗨，我正在写欧几里得算法。在Python中，使用了a=b*k+r的概念。在某些情况下，它可以部分工作，但在接近尾声时会出错。有人能帮我找出我在哪里出错吗？

a = int(input("Enter First Number: "))
b = int(input("Enter Second Number: "))
A = a
B = b
k = 0
r = 1
while (a!=(b*b)):  
    
    while(a>(b*k)):
        k = k+1
        
    k = k-1
    
    r = (a-(b*k))
    a = b
    b = r
  
    print (a,b) #to debug which step it is at
    
print("gcd(",A,",",B,") =",b)

Answer 1

我已经读过你想要做的，但我强烈建议你重新阅读欧几里得算法的定义，以便开始编码它。你试图做的是扰乱k和k的定义，导致你的代码以过度扩展的方式循环。

编码欧几里得算法的一个简单方法是使用它的基于除法的实现。只要记住模代表什么，就可以开始了。

快乐的学习。

Answer 2

感谢大家的建议，我能够做出改变并解决了问题。如果有人想要我的解决方案以供参考，我会发布它。

a = int(input("Enter First Number: "))
b = int(input("Enter Second Number: "))
A = a
B = b
while ((a%b)!=0):  
    K = (a/b)
    k = math.trunc(K)   
    r = (a-(b*k))
    a = b
    b = r
        
print("gcd(",A,",",B,") =",b)