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
_________________
A friend In need Is a friend Indeed
ما الفشل إلا هزيمة مؤقتة تخلق لك فرص النجاح