Il crivello di Eratostene - il più antico crivello dei numeri primi
Il crivello di Eratostene trova tutti i numeri primi fino a un limite senza una sola divisione. Basta contare: cancella un numero ogni due dopo il 2, uno ogni tre dopo il 3 e così via. Ciò che resta sono i numeri primi. Più di duemila anni dopo, è ancora uno dei modi più veloci per elencarli.
Eratostene di Cirene
Eratostene visse all’incirca dal 276 al 194 a.C. e diresse la grande biblioteca di Alessandria. È noto soprattutto per aver misurato le dimensioni della Terra dalla lunghezza delle ombre in due città. Il crivello porta il suo nome perché Nicomaco di Gerasa lo descrisse come il suo metodo nell’Introduzione all’aritmetica, scritta intorno al 100 d.C.
Come funziona il crivello
Scrivi i numeri da 2 a N. Il primo numero, 2, è primo: cancella 4, 6, 8 e ogni altro multiplo di 2. Il numero successivo rimasto, 3, è primo: cancella 9, 12, 15 e così via. Continua con 5, 7 e i numeri successivi rimasti. Un numero che non viene mai cancellato non ha fattori più piccoli, quindi è primo.
Fermarsi alla radice quadrata
Ogni numero composto fino a N ha un fattore primo non più grande della radice quadrata di N. Quindi, appena p² supera N, non resta nulla da cancellare. Per trovare i primi fino a 100 bastano 2, 3, 5 e 7, e per 1000 servono i primi fino a 31.
Quanto è veloce?
Il crivello richiede circa N log log N passi, che crescono solo un po’ più in fretta di N stesso. I computer lo usano ancora, spesso a pezzi come crivello segmentato, per elencare i primi fino a miliardi. Per verificare se un singolo numero grande è primo, altri metodi sono più veloci.
Domande frequenti
Chi ha inventato il crivello di Eratostene?
Prende il nome da Eratostene di Cirene, uno studioso greco del III secolo a.C. La più antica descrizione scritta è di Nicomaco di Gerasa, intorno al 100 d.C.
Perché il crivello inizia a cancellare da p²?
Ogni multiplo più piccolo di p ha un fattore primo più piccolo, quindi un primo più piccolo l’ha già cancellato.
Quanti numeri primi ci sono sotto 1000?
Ci sono 168 numeri primi sotto 1000. Il più grande è 997.
Strumenti correlati
Crivello di Eratostene
Guarda il crivello di Eratostene trovare i numeri primi fino a 100, 200, 500 o 1000. Ogni numero primo cancella i suoi multipli con il proprio colore, passo dopo passo.
Spirale di Ulam
Disegna la spirale di Ulam nel browser. Segna i numeri primi, leggi il polinomio di secondo grado di ogni diagonale e apri la serie ininterrotta di 40 primi di Eulero.
La spirale di Ulam
Come la spirale di Stanisław Ulam del 1963 dispone gli interi su una griglia quadrata, perché i primi si raccolgono su diagonali quadratiche e dove stanno i quaranta primi di Eulero quando la spirale parte da 41.
La congettura di Collatz
Esplora il problema di Collatz 3n+1 nel browser. Segui le successioni grandine, fai crescere un albero di Collatz geometrico ed esplora con lo zoom il frattale di Collatz continuo.
Pronto a provarlo?
Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.
Prova il crivello di Eratostene