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.
2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | |
26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 |
2 | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 17 | 19 | 21 | 23 | 25 | ||||||||||||
27 | 29 | 31 | 33 | 35 | 37 | 39 | 41 | 43 | 45 | 47 | 49 |
2 | 3 | 5 | 7 | 11 | 13 | 17 | 19 | 23 | 25 | |||||||||||||||
29 | 31 | 35 | 37 | 41 | 43 | 47 | 49 |
2 | 3 | 5 | 7 | 11 | 13 | 17 | 19 | 23 | ||||||||||||||||
29 | 31 | 37 | 41 | 43 | 47 | 49 |
2 | 3 | 5 | 7 | 11 | 13 | 17 | 19 | 23 | ||||||||||||||||
29 | 31 | 37 | 41 | 43 | 47 |
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=p2, 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.