我正在尝试用Python编写欧几里得算法,它是用来找到两个非常大的数字的最大公约数。该公式为a = bq + r,其中a和b是您的两个数字,q是b可以整除a的次数,r是余数。
我可以编写代码来找到它,但是如果原始数字不产生余数(r),则算法进入第2步=> b = rx + y。(与第一步相同,但只是将b替换为a,将r替换为b)这两个步骤重复,直到r能够同时整除a和b。
这是我的代码,我还没有想出如何替换值并创建循环直到找到最大公约数。
我可以编写代码来找到它,但是如果原始数字不产生余数(r),则算法进入第2步=> b = rx + y。(与第一步相同,但只是将b替换为a,将r替换为b)这两个步骤重复,直到r能够同时整除a和b。
这是我的代码,我还没有想出如何替换值并创建循环直到找到最大公约数。
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))
a - b*(a//b)
和a % b
是相同的。 - Hugh Bothwell