Il logo di batmath
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.

  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 rp. Se ne deduce che a=p·rp·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.

Commenti

Esercizi proposti

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