Algorithme d'Euclide-PGCD

[issam.abdallah]

Bonjour,

Je vous propose un nouvel élément à utiliser : Algorithme d'Euclide-PGCD

L'algorithme d'Euclide permet de calculer facilement le plus grand diviseur commun entre deux entiers a et b : pgcd(a, b).


Algorithme:

Code :

1
2
3
4
tant que b != 0 faire : 
  b = (a mod b) 
  a = b

Car pgcd(a,b) = pgcd(b, a mod b)

Exemple: a= 7, b = 5

a mod b = 7 mod 5 = 2 ==> ( a = 5 et b = 2 )
a mod b = 5 mod 2 = 1 ==> ( a = 2 et b = 1 )
a mod b = 2 mod 1 = 0 ==> ( a = 1 et b = 0 )

Résultat finale : pgcd( 7 , 5 ) = pgcd (2, 1) = 1

pgcd( 7 , 5 ) = 1 ==> 7 et 5 sont premiers entre eux

Rappel : deux nombres a et b sont premiers entre eux si et seulement si leur plus grand commun diviseur est égal à 1 : pgcd(a, b) = 1.

Qu'en pensez-vous ?

[kwariz]

Bonsoir,

L'algorithme est bon dans la démarche (c'est un des grands classiques) mais celui que tu as écris est incorrect. En plus des prérequis (0<=a<=b), tu écrases ta variable a avec une mauvaise valeur. Cela se repère facilement avec une trace.