Implémenter l'opération GCD en Python

1. Utiliser la récursivité pour implémenter le code du GCD en Python
2. Utiliser une boucle for pour implémenter le code du plus grand diviseur commun en Python
3. Utilisez l’algorithme d’Euclide pour implémenter le code du plus grand diviseur commun en Python
4. Utilisez la fonction math.gcd() pour calculer le plus grand diviseur commun en Python

Le plus grand diviseur commun (GCD), également appelé facteur commun le plus élevé (HCF) de deux valeurs, est le plus grand nombre qui divise les deux nombres donnés. Le plus grand diviseur commun peut également être calculé et implémenté en Python.

Ce tutoriel montre les différentes méthodes pour implémenter le code du plus grand diviseur commun en Python.

Utiliser la récursivité pour implémenter le code du GCD en Python

Une fonction qui s’appelle dans le bloc de définition de fonction est appelée récursivité. La récursivité peut être utilisée pour créer une fonction qui calcule le GCD de deux nombres. Ce processus est très utile pour réduire la longueur du code et est pratique pour minimiser les appels de fonction inutiles.

Le code suivant utilise la récursivité pour implémenter le code du plus grand diviseur commun en 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))

Le programme ci-dessus donne le résultat suivant.

Production:

The gcd is : 12

Utiliser une boucle for pour implémenter le code du plus grand diviseur commun en Python

Une simple boucle for et l’instruction if-else peuvent aider à réaliser la même tâche que les autres méthodes de cet article.

Le code suivant utilise une boucle for pour implémenter le code du plus grand diviseur commun en 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))

Le code ci-dessus donne le résultat suivant.

Production:

The gcd is : 12

Utilisez l’algorithme d’Euclide pour implémenter le code du plus grand diviseur commun en Python

L’algorithme d’Euclide est une autre technique capable de calculer rapidement le plus grand diviseur commun de deux nombres.

L’algorithme d’Euclide se définit sur deux faits majeurs.

• Il n’y a pas de changement dans le PGCD si un plus petit nombre soustrait un plus grand nombre. Par conséquent, nous trouvons finalement le PGCD sur la soustraction continue de la plus grande valeur parmi les deux nombres.
• Si on divise le plus petit nombre, au lieu de soustraire ici, l’algorithme s’arrête automatiquement lorsque le reste 0 est rencontré.

Le programme suivant ci-dessous utilise l’algorithme d’Euclide pour implémenter le code du plus grand diviseur commun en 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))

Le code fournit le résultat suivant.

Production:

The gcd is : 12

Utilisez la fonction math.gcd() pour calculer le plus grand diviseur commun en Python

Maintenant, au lieu de créer une fonction définie par l’utilisateur, nous pouvons simplement utiliser la fonction prédéfinie math.gcd() pour calculer le PGCD de deux nombres. Le module math doit être importé dans le code Python afin d’utiliser la fonction gcd().

Le code suivant utilise la fonction math.gcd() pour calculer le plus grand diviseur commun en Python.

import math

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

Le programme ci-dessus fournit le résultat suivant.

Production:

12

Dans Python 3.5 et supérieur, la fonction gcd est contenue dans le module math. Dans les versions précédentes de Python, la fonction gcd était contenue dans le module fractions. Cependant, depuis Python 3.5, il est désormais obsolète.