Scomposizione di un numero in fattori primi
L'algoritmo qui proposto non richiede alcun commento dal punto di vista matematico. Per quanto riguarda la sua implementazione in javascript abbiamo scelto una strada che può ritenersi la trascrizione quasi integrale del classico procedimento "a mano": dato un numero n cerco i numeri primi che non superino la metà di n e poi provo a dividere n per ciascuno di questi divisori, a partire dal più piccolo, ripetendo eventualmente la divisione fin quando non trovo un resto diverso da zero. Il procedimento ha termine quando il quoziente diventa 1. Per trovare i numeri primi che non superino la metà di n abbiamo usato l'algoritmo del crivello di Eratostene (opportunamente adattato), mentre per controllare se n è primo abbiamo usato l'algoritmo già proposto in un altro esercizio. L'algoritmo proposto non è molto efficiente, soprattutto per numeri grandi, e può essere sicuramente migliorato.
Il codice del programma è il seguente (con numerosi commenti che dovrebbero facilitarne la comprensione):
var pr; //variabile che serve nella chiamata della
funzione primo()
var divisori = new Array();
divisori[0]=0; /*I possibili divisori primi del numero, forniti
dalla funzione eratostene. Il primo elemento è posto
uguale a zero, perché gli array di javascript iniziano da
zero.*/
var molt = new Array();
molt[0]=0; /*La molteplicità dei possibili divisori. Se
è zero vuol dire che il numero in questione non è
un divisore. La funzione eratostene inizializza a zero questo
array.*/
var k; //variabile per indicizzare l'array divisori
function scomponi()
{
numero =
parseInt(document.getElementById('numero').value);
if (isNaN(numero) || numero<1) //controllo
dell'input
{
window.alert("Dato in ingresso non valido.\nInserisci un
intero maggiore o uguale a 1");
document.getElementById('numero').focus();
document.getElementById('numero').select();
return; //L'istruzione causa l'interruzione della
funzione, perché essa non è calcolabile
}
var conferma = true;
if (numero>100000) //richiesta di conferma per input molto
alti
{
conferma=window.confirm("Il dato in ingresso è
molto alto.\n
Il tempo di elaborazione richiesto può anche essere
lungo.\n
Se vuoi continuare premi OK, altrimenti Annulla");
}
if (!conferma)
{
document.getElementById('numero').focus();
document.getElementById('numero').select();
return; //Se l'utente ha premuto Annulla, causa la
conclusione della funzione
}
pr=false;
primo(numero); /*Chiama la funzione per controllare se il
numero è primo, nel qual caso il programma termina, con
il messaggio appropriato*/
if (pr || numero==2 || numero == 3)
{
document.getElementById('uno').innerHTML="Il
numero "+numero+" da te introdotto è
primo.";
document.getElementById('due').innerHTML=""
return;
}
var max = Math.floor(numero/2);
k=0;
eratostene(max); /*Chiama la funzione eratostene, passando il
valore max che costituisce il limite fino a cui calolare i
primi*/
/*Da qui comincia il codice vero e proprio
del programma. Il numero dato viene diviso per ciascuno dei suoi
possibili divisori, a partire dal primo: se il resto della
divisione è zero, la molteplicità è
incrementata di uno e la divisione viene ripetuta, altrimenti si
passa oltre*/
var temp = numero; /*variabile temporanea dove piazzeremo i
quozienti delle divisioni, quando la divisione non dà
resto*/
for (var m=1;m<=k;m++)
{
while (temp%divisori[m]==0 && temp>1)
{
temp=Math.floor(temp/divisori[m]);
molt[m]=molt[m]+1;
}
} //end of for
var uscita="1"; //stringa per formattare
l'output
for (var m=1;m<=k;m++)
{
if (molt[m]>0)
{
if (molt[m]==1)
uscita=uscita+" * "+divisori[m];
if (molt[m]>1)
uscita=uscita+" *
"+divisori[m]+"<sup>"+molt[m]+"</sup>";
}
}
document.getElementById('uno').innerHTML="La
scomposizione in fattori primi del numero "+numero+"
è:";
document.getElementById('due').innerHTML=uscita;
} //end of scomponi()
function eratostene(massimo)
{
var minori=new Array();
minori[0]=0;
minori[1]=0;
for (var i=2;i<=massimo;i++)
{
minori[i]=i; //inizializzazione del setaccio
}
for (i=0;i<=massimo;i++)
{
if (minori[i]!=0)
{
for (var j=2;j*i<=massimo;j++) //ciclo che cancella dal
setaccio i multipli di i
{
minori[j*i]=0;
} //end of internal for
} //end of if
} //end of main for
/*Il codice che segue serve a inserire nella
variabile globale divisori i divisori primi trovati con il ciclo
precedente.*/
for (i=1;i<=massimo;i++) //Piazzo nell'array divisori i
divisori rimasti dopo l'applicazione del crivello
{
if (minori[i]!=0)
{
k++;
divisori[k]=minori[i];
molt[k]=0;
}
}
} //end of eratostene()
function primo(x)
{
for (var p=2;p<=Math.floor(Math.sqrt(x));p++)
{
if (x % p == 0)
{
pr=false;
break;
}
if (x % p != 0)
{
pr=true;
} //end of if
} //end of for
} //end of primo()
function azzera()
{
document.getElementById('numero').value="";
document.getElementById('uno').innerHTML="";
document.getElementById('due').innerHTML="";
} //end of azzera()
Commenti
- In questo codice abbiamo implementato gli algoritmi di controllo se un numero è primo e di ricerca dei primi fimo ad un determinato valore con due funzioni che vengono chiamate dalla funzione principale: in sostanza abbiamo spezzato l'algoritmo in parti, e per alcune parti abbiamo utilizzato un codice già utilizzato in altra sede. E' questo uno dei fondamenti della programmazione ad oggetti (anche se qui il problema è solo sfiorato): per costruire un grosso programma ci si divide il lavoro in modo che ogni gruppo produca un oggetto finito che gli altri usano, anche senza sapere come funziona.
-
Il metodo floor() dell'oggetto Math,
che dunque si richiama con Math.floor(), restituisce
la parte intera di un reale, cioè l'intero
immediatamente precedente od uguale al reale dato. Per
esempio
Math.floor(-1.2) = -2;
Math.floor(5) = 5;
Math.floor(3.7) = 3. - Vedi la pagina contenente osservazioni sull'ordine di esecuzione delle istruzioni Javascript.
Esercizio proposto
-
Modificare l'algoritmo cercando prima i divisori propri del numero in ingresso e successivamente i primi solo tra questi.