Python中的Euclidean算法 / GCD

Question

我正在尝试在python中编写欧几里得算法。这是找到两个非常大的GCD。公式为a = bq r，其中a和b是您的两个数字，q是b均匀划分的次数，r是其余的。

我可以编写代码来找到，但是，如果原始数字不会产生零的剩余（r），则该算法将转到步骤2 => b = rx y。（与第一步相同，而只是为a子b，而b的r）重复了两个步骤，直到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))

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)

Answer 2

尝试此

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)

Answer 3

我知道这是旧帖子，但这是：

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)

取自第四版算法。

注意：如果您的数字真的很大，请尝试通过以下方式增加递归限制。

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

，但要非常非常小心。我能够填充我的12GB RAM并很容易引起冻结。

Answer 4

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

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

Answer 5

我认为欧几里得算法工作的重要条件缺失了，即a＆gt; = b＆gt;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

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