Les Algorithmes Arithmétiques
I. Introduction
Dans ce chapitre, on présentera les algorithmes arithmétiques les plus connus : calculs du PGCD e
du PPCM, recherche des nombres premiers et décomposition en produits des facteurs premiers, la
conversion d’un nombre en base 10 vers le binaire et en hexadécimal. A la fin, on développera le
problème qui convertit un nombre en base b1 en son équivalent en base b2.
II. Le calcul du PGCD
1. Définition
PGCD : Plus Grand Commun Diviseur
Le PGCD de deux entiers m et n noté PGCD(m,n) est le grand entier permettant de diviser m et n.
2. Application
Analyser puis déduire l’algorithme d’une fonction qui permet de déterminer le PGCD de deux entiers
m et n selon les deux méthodes : différence et Euclide.
Méthode de différence
a. Principe
Le principe de cette méthode est :
Chercher le différence de deux valeurs et la ranger dans la valeur la plus grande jusqu’à obtenir la
même valeur.
· Est ce que le nombre de répétitions est connu ?
· Au moins égale combien ?
 

b. Exemples 

                      valeurs de départ ^=10 et n=16 ==) PGCD(10.16)=
 

                                                                           ==) PGCD(4.6)=PGCD(4.2)=PGCD(2.2)
 

          ==)  PGCD=2 

          ==) la valeur la plus grande reçoit la valeur de différence
 

 

Exemple 2:
 

                   valeurs de depart  m=20 et n=20  ===)m=n
 

                                                                          ===)dérictement le PGCD=20
 

         ===) nombre de répétitions peut etre=0;
 

 

 

c. Spécification de la fonction PGCD_Diff
Résultat=PGCD_diff
Traitement =
En cas d’égalité le PGCD_Diff=m
Tant que M <> N chercher la valeur la plus grande
Cette valeur reçoit la différence
Paramètres da la fonction : m et n