Generatore con il crivello di Eratostene (gratis) — elenco dei primi e ricerca dell'ennesimo
Basta indicare un limite superiore per generare l'elenco dei numeri primi con il crivello di Eratostene, visualizzandone i passaggi. Comprende un prospetto da 1 a 100, copre intervalli fino a un milione e permette di cercare a ritroso primi di posizione elevata, come il milionesimo. Strumento gratuito che funziona interamente nel navigatore, senza registrazione.
Il crivello di Eratostene da 1 a 100 (prospetto)
Le caselle verdi sono numeri primi; le altre sono numeri composti eliminati dal crivello.
| 1 | 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 |
| 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 |
| 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 |
| 71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 |
| 81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 |
| 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 |
Il numero 1 è un caso particolare, né primo né composto, e non rientra nella colorazione.
Che cosa fa il crivello di Eratostene
Il crivello di Eratostene è l'algoritmo classico per trovare i numeri primi, che prende il nome dallo studioso greco del III secolo a.C. L'idea è sorprendentemente semplice: prenda ogni numero in ordine a partire da due, lo dichiari primo se non è ancora stato cancellato e poi cancelli tutti i suoi multipli. Cancelli i multipli di due, quindi quelli del tre sopravvissuto, poi quelli del cinque; ripeta fino alla radice quadrata del suo limite e ogni numero ancora in piedi sarà primo.
Indichi a questo strumento un limite superiore e genererà l'elenco dei primi fino a un milione. Mostra il procedimento di cancellazione passo dopo passo, così può seguire con i propri occhi quale primo abbia rimosso quali numeri. Funziona anche all'inverso e risponde alla domanda «qual è l'N-esimo primo?» per posizioni alte quanto la milionesima. Tutto viene calcolato nel suo browser, perciò nulla di quanto inserisce ne esce.
Come generare un elenco di primi
- Inserisca il limite superiore N Indichi un intero fra 2 e 1.000.000. Cominciare da qualcosa di piccolo come 100 rende assai più visibile il meccanismo del crivello.
- Controlli il conteggio e il primo più grande Ottiene quanti primi si trovano fino a N — scritto π(N) — e il maggiore fra essi.
- Segua i passi della cancellazione Con limiti piccoli, ogni fase mostra quale primo sia stato impiegato e quali numeri abbia rimosso.
- Cerchi l'N-esimo primo Inserisca una posizione e lo strumento restituisce il primo che la occupa.
Consigli per sfruttarlo al meglio
- Il crivello di Eratostene ricava con efficienza l'elenco dei numeri primi eliminando via via, dagli interi a partire da due, i multipli di ciascun primo.
- Impostando il limite a non più di quattrocento, si possono osservare passaggio per passaggio quali numeri ciascun primo abbia eliminato.
- È prevista anche la ricerca a ritroso di posizioni elevate, per esempio del milionesimo numero primo: comoda per accertare l'esistenza di primi di molte cifre.
- L'elenco è calcolato sul momento nel navigatore e non comporta alcuna trasmissione di dati a un servente.
Quando torna utile
Studiare gli algoritmi
Il crivello è l'esempio da manuale della complessità O(n log log n), e vederlo all'opera fissa l'idea.
Verificare la propria implementazione
Confronti con questo l'output di un crivello scritto da lei per accertare che produca la sequenza corretta.
Osservare come si distribuiscono i primi
Variare il limite e guardare crescere π(N) dà il senso del teorema dei numeri primi e del suo andamento approssimato N / log N.
Documentarsi sulla crittografia
Gli schemi a chiave pubblica come RSA poggiano su primi grandi, e questa è una via d'accesso per cogliere con quale densità compaiano.
I termini dei primi e del crivello
- Numero primo
- Un numero naturale maggiore o uguale a due i cui unici divisori positivi sono uno e sé stesso. L'uno non conta come primo.
- Numero composto
- Un numero naturale maggiore o uguale a due che non è primo. Sono questi i numeri che il crivello cancella.
- π(N)
- La funzione che dà il conteggio dei primi fino a N, nota come funzione enumerativa dei primi.
- Cancellazione
- Il contrassegnare i multipli di un primo per escluderli dai candidati. È l'operazione che dà il nome all'algoritmo.
- Perché basta la radice quadrata
- Ogni multiplo di un primo maggiore della radice quadrata di N è già stato cancellato come multiplo di un primo più piccolo.
- Teorema dei numeri primi
- Il risultato per cui π(N) è asintotica a N / log N, che descrive quanto rapidamente i primi si diradino.
Domande frequenti
A proposito — perché un algoritmo di duemila anni fa è ancora in uso
Il crivello di Eratostene, attribuito allo studioso greco Eratostene, che nel terzo secolo avanti Cristo diresse la biblioteca di Alessandria, è uno dei più antichi algoritmi di generazione dei numeri primi giunti fino a noi. Che un procedimento concepito oltre duemila anni fa continui a essere insegnato nei corsi di informatica dice molto della sua semplicità e della sua eleganza.
Il meccanismo è sorprendentemente semplice: si dispongono i numeri a partire da due, si assume come primo il minore non ancora eliminato e se ne cancellano tutti i multipli. Ripetendo l'operazione fino alla radice quadrata del limite si ottengono tutti i numeri primi non superiori a esso. Quando serve l'elenco completo, il metodo è assai più efficiente delle divisioni successive applicate a un numero per volta.
La ricerca dei numeri primi enormi continua ancora oggi e progetti di calcolo distribuito individuano di continuo primi di Mersenne di decine di milioni di cifre. Il crivello non serve a quelle scoperte, ma la sua idea di fondo — escludere meccanicamente i multipli — è alla base anche degli algoritmi di verifica più avanzati.