Plus grand commun diviseur de plusieurs nombres

Soyez le premier à donner votre avis sur cette source.

Vue 10 453 fois - Téléchargée 694 fois

Description


Définitions


L'arithmétique élémentaire nous enseigne que le plus grand commun diviseur (PGCD) de deux entiers naturels non nuls est le plus grand des diviseurs communs à ces deux entiers.
Deux nombres sont dits "premiers entre eux" lorsque leur PGCD est 1.
On a évidemment PGCD(a,b) = PGCD(b,a)
 
 

Quelques codes


La fonction pgcd est souvent donnée sous la forme classique:
function pgcd(a, b) { // Algorithme d'Euclide  
  while (b>0) {   
    var r=a%b;  
    a=b;  
    b=r;  
  }   
  return a;  
}


Comme nous nous limitons aux entiers strictement positifs, la première comparaison (b>0) est inutile et il vaut mieux écrire:
function pgcd(a,b) { // a>0, b>0  
  do {  
    var r=a;  
    a=b;  
    b=r%a;  
  } while (b>0);  
  return a;  
}


La fonction pgcd(a,b) choisie dans le fichier "pgcd.js" correspond à cette dernière, écrite d'une manière plus "optimisée", mais nettement moins "lisible":
function pgcd(a,b) { // a>0, b>0  
  do var r=a; while ((b=r%(a=b))>0);  
  return a;  
}


On propose souvent la fonction plus simple:
function pgcd(a,b) {  
  while (a!=b) {if (a>b) a-=b; else b-=a;}  
  return a;  
}

Avantage: elle évite la division (ou modulo).
Inconvénient: regardez ce qui s'y passe lors de l'appel pgcd(100000,2) !

Les adeptes des fonctions récursives peuvent utiliser:
function pgcd(a,b) {return ((a%=b)==0)? b: pgcd(b,a);}


La fonction pgcdArr(n,v) du fichier "pgcd.js", qui calcule le PGCD des n premiers nombres de v (array), est basée sur la relation
PGCD(a,PGCD(b,c)) = PGCD(PGCD(a,b),c) = PGCD(a,b,c).
function pgcdArr(n,v) { // pgcd(v[0],v[1],...,v[n-1]), n >= 2  
  var i,p=pgcd(v[0],v[1]);  
  for (i=2; i<n; i++) p=pgcd(p,v[i]);  
  return p;  
}

 
 

Interface


L'interface est simple et, je l'espère pratique et complet.
- Ajout: le bouton "add" ajoute le nombre introduit.
- Sélection: cliquez sur un nombre (-> fond jaune).
- Modification: le bouton "mod" change la valeur du nombre sélectionné.
- Désélection: (re)cliquez sur le nombre sélectionné (fond jaune).
- Suppression: double-cliquez sur le nombre à supprimer.


Faites directement un test: PGCD

L'exemple complet se trouve sur le fichier: ZIP


Testé avec:
 Firefox  22.0  OK 
 Google Chrome  28.0  OK 
 Internet Explorer  10.0.7  OK 
 Opera  22.0   OK 
 Safari   22.0  OK 

Codes Sources

A voir également

Ajouter un commentaire Commentaires
Messages postés
261
Date d'inscription
mardi 12 décembre 2006
Statut
Membre
Dernière intervention
10 juin 2019

Bonjour habibos,

Pour vous répondre, j'ai hésité entre les deux possibilités suivantes:
1) Indiquer que 440 n'est pas divisible par 9.
2) Montrer que PGCD( 540, 440, 333 ) = 1.

La première met en évidence l'"erreur" de l'auteur du message alors que la seconde montre simplement que le résultat obtenu est juste.

J'ai choisi la seconde car je suis arrivé à la conviction que d'affirmer que l'autre a tort n'est quasiment jamais positif ou efficace.

J'espère donc que vous continuerez à vous intéresser, tester et utiliser des codes proposés par CodeS-SourceS avec un "esprit critique", même si parfois, comme il m'arrive aussi assez fréquemment, on peut se tromper.
Messages postés
15778
Date d'inscription
mardi 11 mars 2003
Statut
Contributeur
Dernière intervention
6 avril 2021
529
Bonjour William, je n'avais pas vérifié, mais 440/9 = 48,8888888888 donc non seulement habibos ne sait pas dire bonjour, mais compter non plus.
Messages postés
261
Date d'inscription
mardi 12 décembre 2006
Statut
Membre
Dernière intervention
10 juin 2019

Bonjour,

La décomposition en facteurs premiers donne:
540 = 2*2*3*3*3*5
440 = 2*2*2*5*11
333 = 3*3*37
(voir Décomposition en facteurs premiers)

Aucun de ces facteurs premiers ne figure simultanément dans tous ces trois nombres.

Ce qui semble montrer que leur plus grand commun diviseur est bien 1.

PGCD(540,440,333) = 1.
il y a erreur de calcul essaye 540 ---- 440---- 333 il vous donne 1 alors que C 9.

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.