Calcular e obter o maior divisor comum e o múltiplo menos comum em Python

O negócio

O seguinte é uma descrição de como calcular e obter o maior divisor comum e o múltiplo menos comum em Python.

  • O maior divisor comum e o múltiplo menos comum de dois inteiros
  • O maior divisor comum e o múltiplo menos comum de três ou mais inteiros

Note-se que as especificações das funções fornecidas na biblioteca padrão diferem consoante a versão Python. Um exemplo de implementação de uma função que não se encontra na biblioteca padrão é também mostrado neste artigo.

  • Python 3.4 ou anterior
    • GCD:fractions.gcd()(apenas dois argumentos)
  • Python 3.5 ou posterior
    • GCD:math.gcd()(apenas dois argumentos)
  • Python 3.9 ou posterior
    • GCD:math.gcd()(apoia mais de três argumentos)
    • menor denominador comum:math.lcm()(apoia mais de três argumentos)

Aqui explicamos o método utilizando a biblioteca padrão Python; NumPy pode ser facilmente utilizado para calcular o maior divisor comum e o múltiplo menos comum para cada elemento de múltiplas arrays.

O maior divisor comum e o múltiplo menos comum de dois inteiros

GCD

Desde Python 3.5, existe uma função gcd() no módulo de matemática. gcd() é um acrónimo para

  • greatest common divisor

Retorna o maior divisor comum do inteiro especificado no argumento.

import math

print(math.gcd(6, 4))
# 2

Note que em Python 3.4 e anteriores, a função gcd() está no módulo de fracções, não no módulo matemático. fracções devem ser importadas e fracções.gcd().

menor denominador comum

A função lcm(), que devolve o múltiplo menos comum, foi adicionada ao módulo de matemática em Python 3.9. lcm é um acrónimo para

  • least common multiple

Devolve o múltiplo menos comum do inteiro especificado no argumento.

print(math.lcm(6, 4))
# 12

Antes de Python 3.8, lcm() não é fornecido, mas pode ser facilmente calculado usando gcd().

lcm(a, b) = a * b / gcd(a, b)

Exemplo de implementação.

def my_lcm(x, y):
    return (x * y) // math.gcd(x, y)

print(my_lcm(6, 4))
# 12

/Uma vez que isto resulta numa flutuação decimal, são utilizadas duas barras de retrocesso para truncar o ponto decimal e devolver um resultado de divisão inteiro. Note-se que não é feito qualquer processamento para determinar se o argumento é ou não um número inteiro.

O maior divisor comum e o múltiplo menos comum de três ou mais inteiros

Python 3.9 ou posterior

Começando com Python 3.9, todas as funções seguintes suportam mais de três argumentos.

  • math.gcd()
  • math.lcm()
print(math.gcd(27, 18, 9))
# 9

print(math.gcd(27, 18, 9, 3))
# 3

print(math.lcm(27, 9, 3))
# 27

print(math.lcm(27, 18, 9, 3))
# 54

*Se quiser calcular o maior divisor comum ou o múltiplo menos comum dos elementos de uma lista, especifique o argumento com isto.

l = [27, 18, 9, 3]
print(math.gcd(*l))
# 3

print(math.lcm(*l))
# 54

Python 3.8 ou anterior

Antes de Python 3.8, a função gcd() suportava apenas dois argumentos.

Para encontrar o maior divisor comum ou o múltiplo menos comum de três ou mais inteiros, não é necessário nenhum algoritmo particularmente complicado; basta calcular o maior divisor comum ou o múltiplo menos comum para cada um dos valores múltiplos, por sua vez, utilizando a função de ordem superior reduzir().

GCD

from functools import reduce

def my_gcd(*numbers):
    return reduce(math.gcd, numbers)

print(my_gcd(27, 18, 9))
# 9

print(my_gcd(27, 18, 9, 3))
# 3

l = [27, 18, 9, 3]
print(my_gcd(*l))
# 3

Mais uma vez, note que antes de Python 3.4, a função gcd() está no módulo de fração, não no módulo de matemática.

menor denominador comum

def my_lcm_base(x, y):
    return (x * y) // math.gcd(x, y)

def my_lcm(*numbers):
    return reduce(my_lcm_base, numbers, 1)

print(my_lcm(27, 9, 3))
# 27

print(my_lcm(27, 18, 9, 3))
# 54

l = [27, 18, 9, 3]
print(my_lcm(*l))
# 54