Le plus grand commun diviseur de deux entiers est le plus grand entier naturel qui divise simultanément ces deux entiers.
Plus aucun jeu, plus aucune énigme, plus aucune chasse au trésor ne vous résisteront !
Ecrire à l'auteur de dCode
Annonces sponsorisées :
Separer les nombres par des espaces, séparer les calculs par un retour à la ligne.
Deux nombres a et b sont dits premiers entre eux si il n'y a aucun nombre à part 1 qui soit à la fois diviseur de a et de b.
Le programme ne gère pas les nombres négatifs. Cependant pour être rigoureux mathématiquement, tout dépend de la définition du PGCD retenue, défini sur N*, il est toujours positif, défini sur Z* il est positif ou négatif, c'est le même à un coefficient -1 près.
Dans ce second cas, pour toutes les solutions proposées l'opposé est aussi valable : PGCD(6,9) = PGCD(-6,9) = PGCD(6,-9) = PGCD(-6,-9) = 3 (ou -3). Par convention, seule la valeur positive est retenue.
// JAVASCRIPT
function pgcd(a,b) {
return (b==0)?a:pgcd(b,a%b);
}
// PHP
function pgcd($a,$b) {
return ($b==0)?$a:pgcd($b,$a%$b);
}
"A=" : ? -> R "B=" : ? -> Y I -> U : 0 -> W : 0 -> V : I -> X While Y <> 0 Int(R/Y) -> Q U -> Z : W -> U : Z-Q*W -> W V -> Z : X -> V : Z-Q*X -> X R -> Z : Y -> R : Z-Q*Y -> Y WhileEnd "U=" : U : "V=" : V "PGCD=" : RTI Texas Instrument
Input "A=", R Input "B=", Y I -> U : 0 -> W : 0 -> V : I -> X While Y <> 0 Int(R/Y) -> Q U -> Z : W -> U : Z-Q*W -> W V -> Z : X -> V : Z-Q*X -> X R -> Z : Y -> R : Z-Q*Y -> Y End Disp "U=", U, "V=3, V Disp "PGCD=", R
En utilisant la décomposition en facteurs premiers :
b = p1^a1 * p2^a2 * ... * pn^an
c = q1^b1 * q2^b2 * ... * qm^bm
Comme PGCD(b,c)=1, aucun des facteurs p n'est égal à un q.
Or PGCD(a,b) = un produit de facteurs p
Et PGCD(a,c) = un produit de facteurs q
PGCD(a,b*c) = un produit de facteurs p et q
Donc PGCD(a,b*c) = PGCD(a,b).PGCD(a,c)
dCodeur se réserve la propriété du code source du script PGCD - Plus grand commun diviseur. Toute demande écrite pour un applet (déchiffrement, chiffrement, encodage, décodage, encryptage, décryptage, traduction, traducteur, conversion, solveur), une fonction (décrypter, encrypter, déchiffrer, chiffrer, décoder, code, traduire, convertir, résoudre) ou un script en langage Java, C++, PHP, Python, etc. pourra être formulée via la page contact.
© 2013 dcode.fr — Le site indispensable pour résoudre les énigmes, les jeux et les chasses au trésor. dCode