Implementar a operação GCD em Python

1. Use a recursão para implementar o código para o GCD em Python
2. Use um loop for para implementar o código do maior divisor comum em Python
3. Use o algoritmo euclidiano para implementar o código do maior divisor comum em Python
4. Use a função math.gcd() para calcular o maior divisor comum em Python

O máximo divisor comum (GCD), também conhecido como o fator comum mais alto (HCF) de dois valores, é o maior número que divide os dois números fornecidos. O maior divisor comum também pode ser calculado e implementado em Python.

Este tutorial demonstra os diferentes métodos para implementar o código do maior divisor comum em Python.

Use a recursão para implementar o código para o GCD em Python

Uma função que chama a si mesma no bloco de definição de função é conhecida como recursão. A recursão pode ser usada para criar uma função que calcula o GCD de dois números. Esse processo é muito útil para reduzir o comprimento do código e é útil para minimizar chamadas de função desnecessárias.

O código a seguir usa recursão para implementar o código do maior divisor comum em Python.

def gcd1(x, y):
    if y == 0:
        return x
    else:
        return gcd1(y, x % y)


x = 72
b = 60

print("The gcd is : ", end="")
print(gcd1(72, 60))

O programa acima fornece o seguinte resultado.

Produção:

The gcd is : 12

Use um loop for para implementar o código do maior divisor comum em Python

Um simples loop for e a instrução if-else podem ajudar a realizar a mesma tarefa que os outros métodos neste artigo.

O código a seguir usa um loop for para implementar o código do maior divisor comum em Python.

def gcd2(a, b):

    if a > b:
        small = b
    else:
        small = a
    for i in range(1, small + 1):
        if (a % i == 0) and (b % i == 0):
            gcd = i

    return gcd


a = 72
b = 60

print("The gcd is : ", end="")
print(gcd2(72, 60))

O código acima fornece o seguinte resultado.

Produção:

The gcd is : 12

Use o algoritmo euclidiano para implementar o código do maior divisor comum em Python

O Algoritmo Euclidiano é outra técnica capaz de calcular rapidamente o maior divisor comum de dois números.

O Algoritmo Euclidiano é definido em dois fatos principais.

• Não há alteração no GCD se um número menor subtrair um número maior. Portanto, acabamos descobrindo o GCD na subtração contínua do maior valor entre os dois números.
• Se dividirmos o número menor, em vez de subtrair aqui, o algoritmo para automaticamente quando o resto 0 é encontrado.

O programa a seguir abaixo usa o Algoritmo Euclidiano para implementar o código do maior divisor comum em Python.

def gcd3(p, q):

    while q:
        p, q = q, p % q

    return p


p = 72
q = 60

print("The gcd is : ", end="")
print(gcd3(72, 60))

O código fornece o seguinte resultado.

Produção:

The gcd is : 12

Use a função math.gcd() para calcular o maior divisor comum em Python

Agora, em vez de fazer uma função definida pelo usuário, podemos simplesmente usar a função math.gcd() predefinida para calcular o GCD de dois números. O módulo math precisa ser importado para o código Python para usar a função gcd().

O código a seguir usa a função math.gcd() para calcular o maior divisor comum em Python.

import math

a = math.gcd(72, 60)
print(a)

O programa acima fornece o seguinte resultado.

Produção:

12

No Python 3.5 e superior, a função gcd está contida no módulo math. Nas versões anteriores do Python, a função gcd estava contida no módulo frações. No entanto, a partir do Python 3.5, ele se tornou obsoleto.