Plus grand commun diviseur de plusieurs nombres

Soyez le premier à donner votre avis sur cette source.

Vue 8 241 fois - Téléchargée 644 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

il y a erreur de calcul essaye 540 ---- 440---- 333 il vous donne 1 alors que C 9.
Messages postés
261
Date d'inscription
mardi 12 décembre 2006
Statut
Membre
Dernière intervention
10 juin 2019
> habibos
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
261
Date d'inscription
mardi 12 décembre 2006
Statut
Membre
Dernière intervention
10 juin 2019
> habibos
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.
Messages postés
14574
Date d'inscription
mardi 11 mars 2003
Statut
Contributeur
Dernière intervention
6 août 2020
426 >
Messages postés
261
Date d'inscription
mardi 12 décembre 2006
Statut
Membre
Dernière intervention
10 juin 2019

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
14574
Date d'inscription
mardi 11 mars 2003
Statut
Contributeur
Dernière intervention
6 août 2020
426 > habibos
Et ça t'empêche de dire bonjour?

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.