Python 中的欧几里德算法/GCD

Question

我正在尝试用 Python 编写欧几里得算法。就是求两个非常大的数的 GCD。公式是a = bq + r 其中a和b是你的两个数，q是b整除a的次数，r是余数。

我可以编写代码来找到它，但是如果原始数字没有产生零的余数 ®，那么算法将转到步骤 2 => b = rx + y。 （与第一步相同，只是简单地将 b 替换为 a，将 r 替换为 b）重复这两个步骤，直到 r 将 a 和 b 均分。

这是我的代码，在找到 GCD 之前，我还没有弄清楚如何进行值的替换和创建循环。

 a = int(input("What's the first number? "))
b = int(input("What's the second number? "))
r = int(a - (b)*int(a/b))

if r == 0:
  print("The GCD of the two choosen numbers is " + str(b))

elif r != 0:
  return b and r
  (b == a) and (r == b)

print("The GCD of the two numbers is " + str(r))

原文由 user3280413 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

a = int(input("What's the first number? "))
b = int(input("What's the second number? "))
r=a%b
while r:
    a=b
    b=r
    r=a%b
print('GCD is:', b)

或者在循环中使用 break ：

 a = int(input("What's the first number? "))
b = int(input("What's the second number? "))
while 1:
    r=a%b
    if not r:
        break
    a=b
    b=r
print('GCD is:', b)

原文由 zhangxaochen 发布，翻译遵循 CC BY-SA 3.0 许可协议