Python中的欧几里德算法/ GCD

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

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

来源

2014-02-06 user3280413

提示 - 'a - b *（a // b）'与'a％b'相同。 –

这应该有助于您开始使用：http://www.tutorialspoint.com/python/python_while_loop.htm – IanAuld

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)

来源

2014-02-06 16:43:15 zhangxaochen

您可以定义一个函数，调用该函数从定义中。试试这个：

#!/usr/bin/env python 

def euclid_algo(n, m): # where n > m 
    r = n % m 
    if r == 0: 
     print "gcd(%d, %d) = %d" %(a, b, m) 
    else: 
     euclid_algo(m, r) 

a = 35047 
b = 101 

euclid_algo(a, b) 

# out[1]: gcd(35047, 101) = 101

来源

2014-02-06 19:00:48 gobrewers14

Python中的欧几里德算法/ GCD

回答

相关问题