python - Python中的欧几里得算法/GCD

Question

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

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

这是我的代码，在找到 GCD 之前，我还没有弄清楚如何对值进行 subbing 并创建一个循环。

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))

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)