Calculer et obtenir le plus grand commun diviseur et le plus petit commun multiple en Python

Affaires

Ce qui suit est une description de la manière de calculer et d'obtenir le plus grand commun diviseur et le plus petit commun multiple en Python.

  • Le plus grand commun diviseur et le plus petit commun multiple de deux entiers
  • Le plus grand commun diviseur et le plus petit commun multiple de trois entiers ou plus.

Notez que les spécifications des fonctions fournies dans la bibliothèque standard diffèrent selon la version de Python. Un exemple d'implémentation d'une fonction qui ne fait pas partie de la bibliothèque standard est également présenté dans cet article.

  • Python 3.4 ou antérieur
    • GCD:fractions.gcd()(seulement deux arguments)
  • Python 3.5 ou supérieur
    • GCD:math.gcd()(seulement deux arguments)
  • Python 3.9 ou supérieur
    • GCD:math.gcd()(soutient plus de trois arguments)
    • moindre dénominateur commun:math.lcm()(soutient plus de trois arguments)

Nous expliquons ici la méthode en utilisant la bibliothèque Python standard ; NumPy peut facilement être utilisé pour calculer le plus grand commun diviseur et le plus petit commun multiple pour chaque élément de plusieurs tableaux.

Le plus grand commun diviseur et le plus petit commun multiple de deux entiers

GCD

Depuis Python 3.5, il existe une fonction gcd() dans le module mathématique. gcd() est l'acronyme de

  • greatest common divisor

Retourne le plus grand diviseur commun de l'entier spécifié dans l'argument.

import math

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

Notez que dans Python 3.4 et antérieur, la fonction gcd() se trouve dans le module fractions, et non dans le module mathématique. Il faut importer fractions et fractions.gcd().

moindre dénominateur commun

La fonction lcm(), qui renvoie le plus petit commun multiple, a été ajoutée au module mathématique dans Python 3.9. lcm est un acronyme de

  • least common multiple

Renvoie le plus petit commun multiple de l'entier spécifié dans l'argument.

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

Avant Python 3.8, lcm() n'est pas fourni, mais peut être facilement calculé en utilisant gcd().

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

Exemple de mise en œuvre.

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

print(my_lcm(6, 4))
# 12

/Comme le résultat est un flottant décimal, deux antislashes sont utilisés pour tronquer le point décimal et renvoyer un résultat de division entier. Notez qu'aucun traitement n'est effectué pour déterminer si l'argument est un entier ou non.

Le plus grand commun diviseur et le plus petit commun multiple de trois entiers ou plus.

Python 3.9 ou supérieur

À partir de Python 3.9, toutes les fonctions suivantes prennent en charge plus de trois arguments.

  • 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

*Si vous voulez calculer le plus grand commun diviseur ou le plus petit commun multiple des éléments d'une liste, spécifiez l'argument avec ceci.

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

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

Python 3.8 ou antérieur

Avant Python 3.8, la fonction gcd() ne supportait que deux arguments.

Pour trouver le plus grand commun diviseur ou le plus petit commun multiple de trois entiers ou plus, aucun algorithme particulièrement compliqué n'est nécessaire ; il suffit de calculer le plus grand commun diviseur ou le plus petit commun multiple pour chacune des valeurs multiples à l'aide de la fonction d'ordre supérieur reduce().

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

Encore une fois, notez qu'avant Python 3.4, la fonction gcd() se trouve dans le module fraction, et non dans le module mathématique.

moindre dénominateur commun

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