Algoritme

typi -  
Hxyp Messages postés 401 Date d'inscription   Statut Membre Dernière intervention   -
Bonjour, j aimerais avoir un cours explicite sur l algorithme d euclide merci d'avance



1 réponse

Réponse 1 / 1
Hxyp Messages postés 401 Date d'inscription   Statut Membre Dernière intervention   54
 
Bonjour,
Comme il l'est indiqué sur wikipedia :
https://fr.wikipedia.org/wiki/Algorithme_d%27Euclide
«L'algorithme d'Euclide est un algorithme permettant de déterminer le plus grand commun diviseur (P.G.C.D.) de deux entiers dont on ne connaît pas la factorisation.»
Dans l'exemple : 
Calculons, par exemple, le PGCD de 1071 et de 1029 à l'aide de l'algorithme d'Euclide :

1071 = 1029 × 1 + 42

1029 = 42 × 24 + 21

42 = 21 × 2 + 0

Il faut prendre le dernier reste avant le zéro, donc PGCD(1071 ; 1029) = 21

C'est le reste de la division (modulo) qui est utilisé :

1071/1029=1
1071-1029*1=42

1029/42=24
1029-42*24=21

42/21=2
42-21*2=0

alors le PGCD est de 21
0