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.
Consigli
- 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.
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.