Algoritme
Fermé
typi
-
28 janv. 2011 à 19:29
Hxyp Messages postés 401 Date d'inscription vendredi 28 janvier 2011 Statut Membre Dernière intervention 27 avril 2014 - 29 janv. 2011 à 15:05
Hxyp Messages postés 401 Date d'inscription vendredi 28 janvier 2011 Statut Membre Dernière intervention 27 avril 2014 - 29 janv. 2011 à 15:05
1 réponse
Hxyp
Messages postés
401
Date d'inscription
vendredi 28 janvier 2011
Statut
Membre
Dernière intervention
27 avril 2014
54
29 janv. 2011 à 15:05
29 janv. 2011 à 15:05
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 :
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
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