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

我已经阅读了您尝试执行的操作，但我强烈建议您再次阅读 Euclidean Algorithm 的定义，以便开始对其进行编码。您试图做的是弄乱 k 的定义，并且 k 导致您的代码以过度扩展的方式循环。

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

祝学习愉快。

Answer 2

感谢大家的建议，我能够进行更改并弄清楚了。如果有人需要参考，我会 post 我的解决方案。

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)

Python 中的欧几里得算法

Euclidean Algorithm in Python

python

python-3.x

algorithm

discrete-mathematics