Plus grand commun diviseur de plusieurs nombres

Télécharger le projet
Commenter

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 

Télécharger le projet

Codes Sources

A voir également

S'inscrire maintenant

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.

Du même auteur (William VOIROL)