www.batmath.it

Ricerca dei primi con il crivello di Eratostene

Il metodo del crivello o setaccio, di Eratostene (grande matematico, astronomo, geografo e filosofo greco, noto al grande pubblico oltre che per il crivello, principalmente per la sua accurata e geniale misura del meridiano terrestre passante per Alessandria d'Egitto) è, probabilmente, l'algoritmo più famoso per cercare i primi, forse perché è di una semplicità disarmante. 

L'idea é questa: scrivi tutti i naturali a partire da 2 fino ad un certo valore n, in un elenco che possiamo chiamare setaccio. Poi comincia a cancellare (setacciare) tutti i multipli del primo numero del setaccio (escluso lui stesso). Prosegui così fino ad arrivare in fondo. I numeri che restano sono i primi minori od uguali a n. E' come se considerassi dei setacci a maglie vie via più larghe: il primo lascia passare solo i multipli di 2, il secondo solo i multipli di 3, e così via.

Nell'esempio che segue abbiamo ricercato i primi fino a 50. Al primo passo abbiamo eliminato i multipli di 2, al secondo quelli di 3, al terzo quelli di 5, al quarto quelli di 7. Da questo punto in poi l'applicazione del procedimento di setacciatura non produce più variazioni: i numeri rimasti nel crivello sono i primi fino a 50.

 

 

 

 

Il procedimento di setacciatura si conclude con il numero 7 perché 7 è il massimo intero il cui quadrato non supera 50 e si può provare che il procedimento di setacciatura per ricercare i primi fino ad un certo numero n può sempre cessare quando si supera la radice quadrata di n. Infatti ogni numero a del setaccio iniziale, contenente tutti i numeri naturali non superiori ad un dato n, cade dal setaccio che corrisponde al più piccolo dei suoi divisori primi. Se indichiamo con p il più piccolo divisore primo di a si ha: a=p·r, con r≥p. Se ne deduce che a=p·r≥p·p=p², da cui p≤√a.

L'implementazione javascript è una semplice traduzione in linguaggio formale dell'algoritmo proposto ed è costituito dalla funzione seguente:

function eratostene()
{
var massimo=parseInt(document.getElementById('numero').value);
if (isNaN(massimo) || massimo<2) //controllo dell'input
{
window.alert("Dato in ingresso non valido.\nInserisci un intero maggiore o uguale a 2");
document.getElementById('numero').focus();
document.getElementById('numero').select();
return; //L'istruzione causa l'interruzione della funzione, perché essa non è calcolabile
}
var conferma = true;
if (massimo>20000) //richiesta di conferma per input molto alti
{
conferma=window.confirm("Il dato in ingresso è molto alto.\nIl 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
}
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<=Math.sqrt(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
var uscita="2"; //stringa dove si scrive, con opportuna formattazione, l'output
for (i=3;i<=massimo;i++) //piazzo in una stringa i primi, separati da un -
{
if (minori[i]!=0)
{
uscita=uscita+" - "+minori[i];
}
}
document.getElementById('uno').innerHTML="I numeri primi minori od uguali a "+massimo+" sono:";
document.getElementById('due').innerHTML=uscita;
} //end of eratostene
function azzera()
{
document.getElementById('numero').value="";
document.getElementById('uno').innerHTML="";
document.getElementById('due').innerHTML="";
}

In sostanza abbiamo costruito un array (dal nome minori) nel quale abbiamo piazzato 0 ai primi due posti e i numeri fino al valore introdotto negli altri posti: questo ci consente di avere il setaccio iniziale con uno zero in corrispondenza alle caselline vuote e con un numero uguale all'indice dell'array nelle altre caselline. Successivamente, a partire dal posto di indice due dell'array, controlliamo se nell'array c'è zero o no: se c'è zero procediamo oltre, altrimenti scriviamo zero in corrispondenza a tutti i multipli dell'indice dell'array e poi procediamo oltre. Alla fine ci resterà un array con tanti zero dove non ci sono primi e con i primi cercati sulle altre caselle.

Commenti

• Nel codice abbiamo anche implementato due tipi di controllo sull' input, uno per evitare errori di digitazione e l'altro per chiedere conferma nel caso di inserimento di numeri molto grandi che richiedono lunghi tempi di elaborazione. Il controllo del primo tipo avviene con il metodo alert() dell'oggetto window, metodo che produce la visualizzazione di una finestra modale (cioè che non consente di proseguire finché non viene chiusa). Il controllo del secondo tipo avviene con il metodo confirm() dell'oggetto window, che propone sempre una finestra modale con due pulsanti: se viene premuto OK restituisce true, altrimenti false.
• Abbiamo anche introdotto una semplice formattazione nel pulsante che chiama la funzione. Gli oggetti per l'input (text, button, textarea, checkbox, ecc.) ammettono limitate possibilità di formattazione, e solo con sofisticate tecniche javascript è possibile fare di più (esempio cambiare il colore di sfondo nelle caselle di testo). Vedere il codice dell'esempio proposto.

Esercizi proposti

• Modificare l'algoritmo in modo da inserire un primo ed un ultimo numero tra cui cercare i primi.
• Modificare l'algoritmo in modo da evitare di considerare i pari nel setaccio iniziale.

copyright 2000 et seq. maddalena falanga & luciano battaia

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