Le plus grand commun diviseur de deux entiers est le plus grand entier naturel qui divise simultanément ces deux entiers.
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)
© 2012 dcode.fr — Le site indispensable pour résoudre les énigmes, les jeux et les chasses au trésor. dCode