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 a≥b>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.