Trouver le Plus Grand Commun Diviseur (PGCD) en C

Introduction

In this lab, you will learn how to find the Greatest Common Divisor (GCD) of two integers using the Euclidean algorithm in a C program. You will start by reading two integers from user input, then apply the Euclidean algorithm to calculate their GCD, and finally print the result. This lab covers fundamental concepts in number theory and discrete mathematics, providing a practical application of these principles using the C programming language.

Lecture de deux entiers

Dans cette étape, vous apprendrez à lire deux entiers à partir de l'entrée utilisateur dans un programme C afin de trouver leur plus grand diviseur commun (PGCD).

Tout d'abord, créons un nouveau fichier C pour notre programme PGCD :

cd ~/project
nano gcd.c

Maintenant, ajoutez le code suivant pour lire deux entiers :

#include <stdio.h>

int main() {
    int num1, num2;

    printf("Entrez le premier entier : ");
    scanf("%d", &num1);

    printf("Entrez le deuxième entier : ");
    scanf("%d", &num2);

    printf("Premier nombre : %d\n", num1);
    printf("Deuxième nombre : %d\n", num2);

    return 0;
}

Décomposons le code :

• scanf() est utilisé pour lire l'entrée entière de l'utilisateur
• %d est le spécificateur de format pour les entiers
• &num1 et &num2 transmettent les adresses mémoire des variables pour stocker l'entrée

Compilons et exécutons le programme :

gcc gcd.c -o gcd
./gcd

Exemple de sortie :

Entrez le premier entier : 48
Entrez le deuxième entier : 18
Premier nombre : 48
Deuxième nombre : 18

Application de l'algorithme d'Euclide

Dans cette étape, vous implémenterez l'algorithme d'Euclide pour trouver le plus grand diviseur commun (PGCD) de deux entiers.

Ouvrez le fichier gcd.c précédent et modifiez-le pour inclure le calcul du PGCD :

cd ~/project
nano gcd.c

Mettez à jour le code avec l'implémentation de l'algorithme d'Euclide :

#include <stdio.h>

// Fonction pour calculer le PGCD en utilisant l'algorithme d'Euclide
int calculateGCD(int a, int b) {
    // Assurer des nombres positifs
    a = (a > 0) ? a : -a;
    b = (b > 0) ? b : -b;

    // Algorithme d'Euclide
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }

    return a;
}

int main() {
    int num1, num2, gcd;

    printf("Entrez le premier entier : ");
    scanf("%d", &num1);

    printf("Entrez le deuxième entier : ");
    scanf("%d", &num2);

    // Calculer le PGCD
    gcd = calculateGCD(num1, num2);

    printf("Premier nombre : %d\n", num1);
    printf("Deuxième nombre : %d\n", num2);
    printf("Plus grand diviseur commun : %d\n", gcd);

    return 0;
}

Décomposons l'implémentation de l'algorithme d'Euclide :

• L'algorithme divise itérativement le plus grand nombre par le plus petit.
• Il utilise l'opérateur modulo % pour obtenir le reste.
• Le processus continue jusqu'à ce que le reste devienne 0.
• Le dernier reste non nul est le PGCD.

Compilons et exécutons le programme :

gcc gcd.c -o gcd
./gcd

Exemple de sortie :

Entrez le premier entier : 48
Entrez le deuxième entier : 18
Premier nombre : 48
Deuxième nombre : 18
Plus grand diviseur commun : 6

Affichage du PGCD

Dans cette étape, vous formaterez et afficherez le résultat du PGCD avec un contexte supplémentaire pour rendre la sortie plus informative.

Ouvrez le fichier gcd.c précédent et ajoutez un formatage à la sortie :

cd ~/project
nano gcd.c

Mettez à jour le code pour améliorer la sortie du PGCD :

#include <stdio.h>

// Fonction pour calculer le PGCD en utilisant l'algorithme d'Euclide
int calculateGCD(int a, int b) {
    // Assurer des nombres positifs
    a = (a > 0) ? a : -a;
    b = (b > 0) ? b : -b;

    // Algorithme d'Euclide
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }

    return a;
}

int main() {
    int num1, num2, gcd;

    printf("Calculateur du Plus Grand Diviseur Commun (PGCD)\n");
    printf("------------------------------------------------\n");

    printf("Entrez le premier entier : ");
    scanf("%d", &num1);

    printf("Entrez le deuxième entier : ");
    scanf("%d", &num2);

    // Calculer le PGCD
    gcd = calculateGCD(num1, num2);

    // Sortie formatée
    printf("\nRésultats :\n");
    printf("Premier nombre :  %d\n", num1);
    printf("Deuxième nombre : %d\n", num2);
    printf("PGCD :           %d\n", gcd);

    // Explication supplémentaire
    printf("\nExplication :\n");
    printf("Le Plus Grand Diviseur Commun (PGCD) est le plus grand entier positif\n");
    printf("qui divise les deux nombres sans laisser de reste.\n");

    return 0;
}

Compilons et exécutons le programme :

gcc gcd.c -o gcd
./gcd

Exemple de sortie :

Calculateur du Plus Grand Diviseur Commun (PGCD)
------------------------------------------------
Entrez le premier entier : 48
Entrez le deuxième entier : 18

Résultats :
Premier nombre :  48
Deuxième nombre : 18
PGCD :           6

Explication :
Le Plus Grand Diviseur Commun (PGCD) est le plus grand entier positif
qui divise les deux nombres sans laisser de reste.

Améliorations clés :

• Ajout d'un titre et d'un séparateur.
• Formatage de la sortie avec des colonnes alignées.
• Inclusion d'une explication du concept de PGCD.
• Conservation de la logique de calcul du PGCD de base.

Résumé

Dans ce laboratoire, vous avez d'abord appris à lire deux entiers à partir de l'entrée utilisateur en utilisant la fonction scanf(). Vous avez ensuite implémenté l'algorithme d'Euclide pour calculer le plus grand diviseur commun (PGCD) des deux nombres. L'algorithme d'Euclide est un moyen efficace de trouver le PGCD en appliquant de manière répétée l'opération modulo jusqu'à ce que le reste devienne zéro, auquel cas le PGCD est le dernier reste non nul. Enfin, vous avez affiché le PGCD calculé.