欧几里得算法 / Python中的最大公约数

Question

我正在尝试用Python编写欧几里得算法，它是用来找到两个非常大的数字的最大公约数。该公式为a = bq + r，其中a和b是您的两个数字，q是b可以整除a的次数，r是余数。

我可以编写代码来找到它，但是如果原始数字不产生余数（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))

- user3280413

---

提示 - a - b*(a//b) 和 a % b 是相同的。 - Hugh Bothwell

这应该能帮助你入门：http://www.tutorialspoint.com/python/python_while_loop.htm - kylieCatt

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

Answer 2

我认为这是最简短的解决方案：

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

- Jurakin

Answer 3

尝试这个。

a = int(input("Enter No.1"))

b = int(input("Enter No.2"))

r = a%b

q = int(a/b)

while(r!=0):

    a = b

    b = r

    q = int(a/b)

    r = a - (b * q)


print(b)

- vivek shinde

Answer 4

我知道这是旧帖，但在此提供：

def GCD(x , y):
    """This is used to calculate the GCD of the given two numbers.
    You remember the farm land problem where we need to find the 
    largest , equal size , square plots of a given plot?"""
    if y == 0:
        return x
    r = int(x % y)
    return GCD(y , r)

引自《算法 第4版》。

注意：如果你的数字非常大，那么可以尝试通过以下方式增加递归限制：

import sys
sys.seterecursionlimit("your new limit")

但要非常小心。我曾经轻易地填满了我的12GB内存，导致电脑冻结。

- Ahmad Khalil

Answer 5

我认为欧几里得算法能够正常工作的前提条件之一是a >= b > 0。因此，我建议使用我刚刚编写的代码（由于在构建代码之前没有查看先前的答案，所以代码相对较长）。

def gcd(int1: int, int2: int):
# I used a recursive algorithm
# Condition: a>=b>0
if int1 < int2:
    a = int2
    b = int1
else:
    a = int1
    b = int2

if a % b == 0:
    return b
else:
    r = a % b
    gcd(b, r)
    return r

- amateuraspirant484

Answer 6

最近我在数学课上遇到了这样一个问题。我写的代码是：

def EuclideanAlg(a,b):
    # switches the value of a and b if a is less than b
    if a <= b - 1:
        temp = a
        a = b
        b = temp
    # takes the remainder after a is divided by b
    r = a % b
    # iterates infinitely
    while True:
        # if a is divisible by b, b is the gcd of a,b
        if r == 0:
            return b
            break
        # a becomes the current value of b and b becomes the current value of r
        else:
            temp = r
            r = b % r
            b = temp

- Rueben Purell