programa - Código para el Divisor común más grande en Python

minimo comun multiplo 2 numeros python

Question

El mayor divisor común (GCD) de ayb es el número más grande que los divide a ambos sin resto.

Una forma de encontrar el GCD de dos números es el algoritmo de Euclides, que se basa en la observación de que si r es el resto cuando a se divide por b , entonces gcd(a, b) = gcd(b, r) . Como caso base, podemos usar gcd(a, 0) = a .

Escribe una función llamada gcd que toma los parámetros a y b y devuelve su máximo común divisor.

Answer 1

Este código calcula el gcd de más de dos números dependiendo de la opción dada por # el usuario, aquí el usuario da el número

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 2

Para 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

Para 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 3

Creo que otra forma es usar recursión. Aquí está mi código:

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 4

El intercambio de valores no funcionó bien para mí. Así que configuré una situación similar a un espejo para los números que se ingresan en a <b OR 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 5

Está en la biblioteca estándar .

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

Código fuente del módulo de inspect en 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

A partir de Python 3.5, gcd está en el módulo math ; el uno en fractions está en desuso. Además, inspect.getsource ya no devuelve el código fuente explicativo de ninguno de los métodos.

Answer 6

Esta versión de código utiliza el algoritmo de Euclid para encontrar GCD.

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

Answer 7

Los algoritmos con mn pueden correr terriblemente largo.

Este funciona mucho mejor:

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

Answer 8

Una solución muy concisa usando la recursión:

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

Answer 9

en python con recursión:

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

Answer 10

#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 11

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)

Un enfoque diferente basado en el algoritmo de euclides.

Answer 12

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

Answer 13

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

Answer 14

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

Answer 15

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 16

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