Calcul du PGCD avec l’Algorithme d’Euclide

Dans ce tutoriel, nous allons utiliser l’Algorithme d’Euclide pour le calcul du PGCD.

Définition mathématique du PGCD (Plus Grand Commun Diviseur) :

Le PGCD de deux nombres entiers (a) et (b), noté (\text{PGCD}(a, b)), est le plus grand nombre entier qui divise à la fois (a) et (b) sans laisser de reste.

Algorithme d’Euclide pour calculer le PGCD :

L’algorithme d’Euclide est une méthode efficace pour calculer le PGCD de deux nombres. Voici les étapes de l’algorithme :

Initialisation : Soit (a) et (b) les deux nombres dont nous voulons trouver le PGCD.
Division : Divisez (a) par (b) et obtenez le reste (r).
Test du reste : Si (r) est égal à zéro, alors (b) est le PGCD.
Répétition : Sinon, remplacez (a) par (b) et (b) par (r), puis retournez à l’étape 2.

L’algorithme continue ce processus jusqu’à ce que le reste devienne zéro. À ce moment-là, le dernier diviseur non nul (c’est-à-dire la dernière valeur de (b)) est le PGCD recherché.

Exemple :
Prenons les nombres (a = 48) et (b = 18) pour illustrer l’algorithme d’Euclide :

(48) divisé par (18) donne un quotient de (2) et un reste de (12).
Remplaçons (a) par (b) et (b) par (r), donc maintenant (a = 18) et (b = 12).
Répétons le processus : (18) divisé par (12) donne un quotient de (1) et un reste de (6).
Encore une fois, remplaçons (a) par (b) et (b) par (r), donc maintenant (a = 12) et (b = 6).
Continuons jusqu’à ce que le reste soit zéro. Les étapes suivantes donneront (a = 6), (b = 0), et le PGCD est (6).

Ainsi, (\text{PGCD}(48, 18) = 6).

Javascript

L’algorithme d’Euclide est une méthode classique pour calculer le PGCD de deux nombres. Voici un exemple d’implémentation de l’algorithme d’Euclide en JavaScript :

// Fonction pour calculer le PGCD avec l'algorithme d'Euclide
function euclideanGCD(a, b) {
    while (b !== 0) {
        const temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// Exemples d'utilisation
const example1 = euclideanGCD(48, 18);
console.log("PGCD de 48 et 18 :", example1);

const example2 = euclideanGCD(60, 72);
console.log("PGCD de 60 et 72 :", example2);

Dans cet exemple, la fonction euclideanGCD prend deux paramètres, a et b, et utilise l’algorithme d’Euclide pour calculer leur PGCD. La boucle while est utilisée pour itérer jusqu’à ce que b devienne zéro, et à chaque itération, les valeurs de a et b sont mises à jour en fonction des opérations modulo. La fonction renvoie le PGCD une fois que b atteint zéro.

Les exemples d’utilisation démontrent comment utiliser cette fonction pour calculer le PGCD de deux paires de nombres (48, 18) et (60, 72). Vous pouvez remplacer ces valeurs par d’autres nombres pour effectuer d’autres calculs.

Python

Voici un exemple d’implémentation de l’algorithme d’Euclide pour calculer le PGCD en Python :

def euclidean_gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

# Exemples d'utilisation
example1 = euclidean_gcd(48, 18)
print("PGCD de 48 et 18 :", example1)

example2 = euclidean_gcd(60, 72)
print("PGCD de 60 et 72 :", example2)

Dans cet exemple Python, la fonction euclidean_gcd réalise le même algorithme d’Euclide que dans l’exemple JavaScript. La boucle while est utilisée pour itérer jusqu’à ce que b soit égal à zéro, et à chaque itération, les valeurs de a et b sont mises à jour en fonction des opérations modulo. La fonction renvoie le PGCD une fois que b atteint zéro.

Les exemples d’utilisation montrent comment utiliser cette fonction pour calculer le PGCD de deux paires de nombres (48, 18) et (60, 72). Vous pouvez remplacer ces valeurs par d’autres nombres pour effectuer d’autres calculs en Python.

C

Voici un exemple d’implémentation de l’algorithme d’Euclide pour calculer le PGCD en langage C :

#include <stdio.h>

int euclidean_gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int main() {
    // Exemples d'utilisation
    int example1 = euclidean_gcd(48, 18);
    printf("PGCD de 48 et 18 : %d\n", example1);

    int example2 = euclidean_gcd(60, 72);
    printf("PGCD de 60 et 72 : %d\n", example2);

    return 0;
}

Dans ce programme en langage C, la fonction euclidean_gcd implémente l’algorithme d’Euclide. La boucle while est utilisée pour itérer jusqu’à ce que b soit égal à zéro, et à chaque itération, les valeurs de a et b sont mises à jour en utilisant l’opération modulo. La fonction renvoie le PGCD une fois que b atteint zéro.

Le programme principal (main) utilise cette fonction pour calculer le PGCD de deux paires de nombres (48, 18) et (60, 72). Les résultats sont ensuite affichés à l’aide de la fonction printf. Vous pouvez remplacer les valeurs pour effectuer d’autres calculs en langage C.