Il logo di batmath
www.batmath.it

Massimo comun divisore di due numeri

Questa pagina ha due obiettivi didattici :

La ricerca del massimo comun divisore di due numeri a e b è fatta, di solito, seguendo l'algoritmo "standard": si cercano i divisori di a e b e poi si prendono i divisori comuni con il minimo esponente. Questo algoritmo è sufficiente per numeri che hanno divisori primi piccoli, ma basta provare, per esempio, con la coppia (4687, 2279) per toccare con mano la difficoltà pratica di un simile procedimento. 

Esiste un algoritmo molto più efficiente, scoperto già da Euclide (Elementi, Libro VII, pr.1), e di immediata implementazione in un linguaggio informatico. L'algoritmo si basa sul seguente

Teorema: Se a e b sono naturali con ab>0 e a=bq+r, d é un divisore di a e b se e solo se é un divisore di b ed r.
La dimostrazione è immediata: poiché r=a-bq  ogni divisore di a e b é anche un divisore di r; viceversa poiché a=bq+r, ogni divisore di b ed r é anche un divisore di a.

Si può allora procedere eseguendo successivamente le divisioni intere: a=bq0+r0, b=r0q1+r1, r0=r1q2+r2, ecc., fin quando si ottiene come resto zero. Il penultimo resto è il massimo comun divisore cercato.

L'implementazione javascript è addirittura banale e si compone delle poche righe evidenziate in grassetto nella funzione qui sotto. Il resto è solo controllo dell'input e scambio dei numeri in ingresso in modo da avere come primo numero il maggiore dei due (perché nel fare la divisione si fa il più grande diviso il più piccolo).

function calcola()
{
var num1=parseInt(document.getElementById('numero1').value);
var num2=parseInt(document.getElementById('numero2').value);
if (isNaN(num1) || isNaN(num2)|| num1<0 || num2<0) //controllo dell'input
  {
  window.alert("Dati in ingresso non validi.\nInserisci interi maggiori o uguali a 0.");
  return; //L'istruzione causa l'interruzione della funzione, perchè essa non è calcolabile
  }
if (num1<num2) //scambio in modo da avere num1 sempre più grande
  {
  var temp;
  temp=num1;
  num1=num2;
  num2=temp;
  }
if (num2==0) //Se il numero più piccolo è zero l'MCD è il più grande (anche quando il più grande è zero, per def).
  {
  document.getElementById('risultato').value=("Il massimo comun divisore tra "+num1+" e "+num2+" è "+num1);
  return; 
  }
var x=num1;
var y=num2;
var r;
while (y>0)
  {
  r=x % y;
  x = y;
  y = r;
  }

document.getElementById('risultato').value=(" Il massimo comun divisore tra "+num1+" e "+num2+" è "+x+".");
} //end of calcola()

Per contro l'implementazione con l'algoritmo "standard" (quello che ci ha tanto fatto penare sui banchi della scuola media!!) è lunga e laboriosa e invitiamo i volenterosi a provare a realizzarla utilizzando il codice, opportunamente adattato, del programma per la scomposizione in fattori.

Commenti

Esercizi proposti

pagina pubblicata il 01/11/2001 - ultimo aggiornamento il 01/09/2003