Największy wspólny dzielnik (GCD) a i b to największa liczba, która dzieli oba z nich bez reszty.

Jednym ze sposobów znalezienia GCD dwóch liczb jest algorytm Euklidesa, który opiera się na obserwacji, że jeśli rjest to reszta, kiedy ajest podzielona przez b, to gcd(a, b) = gcd(b, r). Jako podstawę możemy użyć gcd(a, 0) = a.

Napisz funkcję zwaną GCD, który wymaga parametrów aa bi zwraca ich największy wspólny dzielnik.

Znajduje się w standardowej bibliotece .

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

Kod źródłowy z inspectmodułu w Pythonie 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

Od wersji Python 3.5 gcd znajduje się w mathmodule ; ten w fractionsjest przestarzały. Ponadto inspect.getsourcenie zwraca już wyjaśniającego kodu źródłowego dla żadnej z metod.

Algorytmy z mn mogą działać bardzo długo.

Ten działa znacznie lepiej:

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

Ta wersja kodu wykorzystuje algorytm Euclid do znajdowania GCD.

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

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

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

Bardzo zwięzłe rozwiązanie wykorzystujące rekurencję:

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

używając rekurencji ,

def gcd(a,b):
    return a if not b else gcd(b, a%b)

używanie while ,

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

za pomocą lambdy,

gcd = lambda a,b : a if not b else gcd(b, a%b)

>>> gcd(10,20)
>>> 10

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)

Inne podejście oparte na algorytmie Euclid.

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)

Myślę, że innym sposobem jest użycie rekurencji. Oto mój kod:

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

w Pythonie z rekurencją:

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

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

Dla 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

Dla jednego a>blub 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

Musiałem zrobić coś takiego dla zadania domowego przy użyciu pętli while. Nie jest to najbardziej efektywny sposób, ale jeśli nie chcesz używać funkcji, działa to:

num1 = 20
num1_list = []
num2 = 40
num2_list = []
x = 1
y = 1
while x <= num1:
    if num1 % x == 0:
        num1_list.append(x)
    x += 1
while y <= num2:
    if num2 % y == 0:
        num2_list.append(y)
    y += 1
xy = list(set(num1_list).intersection(num2_list))
print(xy[-1])

def _grateest_common_devisor_euclid(p, q):
    if q==0 :
        return p
    else:
        reminder = p%q
        return _grateest_common_devisor_euclid(q, reminder)

print(_grateest_common_devisor_euclid(8,3))

Ten kod oblicza gcd więcej niż dwóch liczb w zależności od wyboru podanego przez # użytkownika, tutaj użytkownik podaje liczbę

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

Zamiana wartości nie działała dobrze dla mnie. Więc po prostu skonfigurowałem sytuację podobną do lustra dla liczb, które są wprowadzane w a <b LUB 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)

#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: ",

great_common_devisor (A)

def gcdIter(a, b):
gcd= min (a,b)
for i in range(0,min(a,b)):
    if (a%gcd==0 and b%gcd==0):
        return gcd
        break
    gcd-=1

Oto rozwiązanie wdrażające koncepcję Iteration:

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

    returns: a positive integer, the greatest common divisor of a & b.
    '''
    if a > b:
        result = b
    result = a

    if result == 1:
        return 1

    while result > 0:
        if a % result == 0 and b % result == 0:
            return result
        result -= 1