Python中最大公約數的代碼

Question

a和b的最大公約數（GCD）是除了它們之外沒有餘數的最大公約數。找兩個數字的GCD

一種方法是歐幾里得的算法，這是基於這樣的觀察，如果r是餘數a由b分，然後gcd(a, b) = gcd(b, r)。作爲基礎案例，我們可以使用gcd(a, 0) = a。

編寫一個名爲gcd的函數，其參數爲a和b並返回其最大公約數。

Answer 1

這是in the standard library。從inspect模塊

>>> from fractions import gcd 
>>> gcd(20,8) 
4 

源代碼在Python 2.7：

>>> print inspect.getsource(gcd) 
def gcd(a, b): 
    """Calculate the Greatest Common Divisor of a and b. 

    Unless b==0, the result will have the same sign as b (so that when 
    b is divided by it, the result comes out positive). 
    """ 
    while b: 
     a, b = b, a%b 
    return a 

對於Python 3.5，gcdis in the math module; fractions已被棄用。此外，inspect.getsource不再返回任何方法的解釋性源代碼。

Answer 2

此代碼計算取決於由＃給用戶選擇兩個以上數量的GCD，在這裏用戶給出數

numbers = []; 
count = input ("HOW MANY NUMBERS YOU WANT TO CALCULATE GCD?\n") 
for i in range(0, count): 
    number = input("ENTER THE NUMBER : \n") 
    numbers.append(number) 
numbers_sorted = sorted(numbers) 
print 'NUMBERS SORTED IN INCREASING ORDER\n',numbers_sorted 
gcd = numbers_sorted[0] 

for i in range(1, count): 
    divisor = gcd 
    dividend = numbers_sorted[i] 
    remainder = dividend % divisor 
    if remainder == 0 : 
    gcd = divisor 
    else : 
    while not remainder == 0 : 
     dividend_one = divisor 
     divisor_one = remainder 
     remainder = dividend_one % divisor_one 
     gcd = divisor_one 

print 'GCD OF ' ,count,'NUMBERS IS \n', gcd 

Answer 3

的價值交換，並沒有爲我很好地工作。所以我剛剛成立數字鏡子般情況被在任何一個< B或A進入> B：

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

print gcd(18, 2) 

Answer 4

a=int(raw_input('1st no \n')) 
b=int(raw_input('2nd no \n')) 

def gcd(m,n): 
    z=abs(m-n) 
    if (m-n)==0: 
     return n 
    else: 
     return gcd(z,min(m,n)) 


print gcd(a,b) 

基於Euclid算法不同的方法。

Answer 5

def gcd(m,n): 
    return gcd(abs(m-n), min(m, n)) if (m-n) else n 

Answer 6

使用m-n的算法可以運行得非常長。

這一個執行好得多：

def gcd(x, y): 
    while y != 0: 
     (x, y) = (y, x % y) 
    return x 

Answer 7

def gcdRecur(a, b): 
    ''' 
    a, b: positive integers 

    returns: a positive integer, the greatest common divisor of a & b. 
    ''' 
    # Base case is when b = 0 
    if b == 0: 
     return a 

    # Recursive case 
    return gcdRecur(b, a % b) 

Answer 8

在Python遞歸：

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

Answer 9

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

Answer 10

對於a>b：

def gcd(a, b): 

    if(a<b): 
     a,b=b,a 

    while(b!=0): 
     r,b=b,a%r 
     a=r 
    return a 

---

對於任何a>b或a<b：

def gcd(a, b): 

    t = min(a, b) 

    # Keep looping until t divides both a & b evenly 
    while a % t != 0 or b % t != 0: 
     t -= 1 

    return t 

Answer 11

這個版本的代碼利用Euclid算法尋找GCD。

def gcdIter(a, b): 
    if b == 0: 
     return a 
    else: 
     return gcdIter(b, a % b) 

Answer 12

#This program will find the hcf of a given list of numbers. 

A = [65, 20, 100, 85, 125]  #creates and initializes the list of numbers 

def greatest_common_divisor(_A): 
    iterator = 1 
    factor = 1 
    a_length = len(_A) 
    smallest = 99999 

#get the smallest number 
for number in _A: #iterate through array 
    if number < smallest: #if current not the smallest number 
    smallest = number #set to highest 

while iterator <= smallest: #iterate from 1 ... smallest number 
for index in range(0, a_length): #loop through array 
    if _A[index] % iterator != 0: #if the element is not equally divisible by 0 
    break #stop and go to next element 
    if index == (a_length - 1): #if we reach the last element of array 
    factor = iterator #it means that all of them are divisibe by 0 
iterator += 1 #let's increment to check if array divisible by next iterator 
#print the factor 
print factor 

print "The highest common factor of: ", 
for element in A: 
    print element, 
print " is: ", 

greatest_common_devisor（A）

Answer 13

我覺得另一種方法是使用遞歸。這裏是我的代碼：

def gcd(a, b): 
    if a > b: 
     c = a - b 
     gcd(b, c) 
    elif a < b: 
     c = b - a 
     gcd(a, c) 
    else: 
     return a 

Answer 14

gcd = lambda m,n: m if not n else gcd(n,m%n)