Il matematico greco ERATOSTENE (275 - 194 aC) ha applicato un metodo nuovo e facile per determinare se i numeri di una lista sono primi o meno. A partire dai piccoli numeri primi conosciuti, 2, 3, 5, 7, 11, 13, 17, 21, ecc., è chiaro che tutti i loro multipli non sono numeri primi ma composti. Ha ordinato una lista di numeri naturali in ordine ascendente e poi ha rimosso tutti i multipli dei primi numeri primi per identificare il resto dei numeri primi più grandi in quella lista. Illustreremo questo metodo in seguito su un elenco di numeri che vanno da 2 a 100:

• Number 2 is prime, so we remove from this string all the multiples of 2: 2 × 2 = 4; 2 × 3 = 6; 2 × 4 = 8; 2 × 5 = 10; 2 × 6 = 12; 2 × 7 = 14; 2 × 8 = 16; 2 × 9 = 18; 2 × 10 = 20; ... and so on up to 2 × 50 = 100. 2 × 51 = 102, is greater than 100, so we stop.
• Multipli di 2 per rimuovere dalla lista: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98, 100 (numeri due per due).
• 3 è il prossimo numero primo, quindi rimuoveremo dalla lista tutti i multipli di 3: 3 × 2 = 6 (che è già stato rimosso dalla lista, essendo un multiplo di 2); 3 × 3 = 9; 3 × 4 = 12 (che è già stato rimosso dalla lista, essendo un multiplo di 2); 3 × 5 = 15; 3 × 6 = 18 (che è già stato rimosso dalla lista, essendo un multiplo di 2); ... e così via fino a: 3 × 33 = 99. 3 × 34 = 102, è maggiore di 100 quindi ci fermiamo.
• Multipli di 3 per rimuovere dalla lista: 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45, 48, 51, 54, 57, 60, 63, 66, 69, 72, 75, 78, 81, 84, 87, 90, 93, 97, 99 (tre per tre numeri). Se non guardiamo i multipli di 2 che sono già stati rimossi dalla lista, abbiamo ancora: 9, 15, 21, 27, 33, 39, 45, 51, 57, 63, 69, 75, 81, 87, 93, 99, vale a dire. numeri che hanno come fattori solo numeri primi maggiori o uguali a 3: 3 × 3 = 9; 3 × 5 = 15; 3 × 7 = 21; 3 × 9 = 3 × 3 × 3 = 27; 3 × 11 = 33; 3 × 13 = 39; 3 × 15 = 3 × 3 × 5 = 45; 3 × 17 = 51; 3 × 19 = 57; 3 × 21 = 3 × 3 × 7 = 63; 3 × 23 = 69; 3 × 25 = 3 × 5 × 5 = 75; 3 × 27 = 3 × 3 × 3 × 3 = 81; 3 × 29 = 87; 3 × 31 = 93; 3 × 33 = 3 × 3 × 11 = 99.

• Procederemo anche con il seguente numero primo, 5: 5 × 2 = 10 (che è già stato rimosso dalla lista, essendo un multiplo di 2); 5 × 3 = 15 (che è già stato rimosso dalla lista, essendo un multiplo di 3); 5 × 4 = 20 (che è già stato rimosso dalla lista, essendo un multiplo di 2); 5 × 5 = 25; 5 × 6 = 30 (che è già stato rimosso dalla lista, essendo sia un multiplo di 2 e 3); 5 × 7 = 35; ... e così via fino a: 5 × 20 = 100 (che è già stato rimosso dalla lista, essendo un multiplo di 2). 5 × 21 = 105, è maggiore di 100, quindi ci fermiamo.
• Multipli di 5 per rimuovere dalla lista: 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85, 90, 95, 100 (numeri cinque per cinque). Se non guardiamo i multipli di 2 e 3, che sono già stati rimossi dalla lista, dobbiamo ancora rimuovere: 25, 35, 55, 65, 85, 95, es. esattamente i numeri che hanno come fattori solo numeri primi maggiori o uguali a 5: 5 × 5 = 25; 5 × 7 = 35; 5 × 11 = 55; 5 × 13 = 65; 5 × 17 = 85; 5 × 19 = 95.
• Quindi facciamo lo stesso con il seguente numero primo, 7: 7 × 2 = 14 (che è già stato rimosso dalla lista, essendo un multiplo di 2); 7 × 3 = 21 (che è già stato rimosso dalla lista, essendo un multiplo di 3); 7 × 4 = 28 (che è già stato rimosso dalla lista, essendo un multiplo di 2); 7 × 5 = 35 (che è già stato rimosso dalla lista, essendo un multiplo di 5); 7 × 6 = 42 (che è già stato rimosso dalla lista, essendo sia un multiplo di 2 e 3); ... 7 × 7 = 49; ... e così via fino a: 7 × 14 = 98 (che è già stato rimosso dalla lista, essendo un multiplo di 2). 7 × 15 = 105, è maggiore di 100, quindi ci fermiamo.
• Multipli di 7 da rimuovere dalla lista: 14, 21, 28, 35, 42, 49, 56, 63, 70, 77, 84, 91, 98 (numeri sette per sette). Se non guardiamo i multipli di 2, 3 e 5, che sono già stati rimossi dalla lista, dobbiamo ancora rimuovere: 49, 77, 91, es. esattamente i numeri che hanno come divisori solo numeri primi maggiori o uguali a 7: 7 × 7 = 49; 7 × 11 = 77; 7 × 13 = 91.
• Il prossimo numero primo nella lista è 11 e dovremmo rimuovere dalla lista i multipli di 11; Tuttavia, come abbiamo visto sopra, dovremmo rimuovere solo dai numeri di lista che hanno come divisori solo numeri primi maggiori o uguali a 11. Ma già 11 × 11 = 121 è maggiore di 100, significa che tutti i numeri rimasti in la lista dopo il processo sopra descritto sono già numeri primi.
• Dopo aver rimosso dalla lista tutti i multipli dei numeri primi: 2, 3, 5 e 7, abbiamo ancora nella lista: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, cioè la lista dei numeri primi da 2 a 100.

Che cosa è un numero primo?

Che cosa è un numero composto?

I numeri primi fino a 1.000

I numeri primi fino a 10.000

Il crivello di Eratostene

Algoritmo di Euclide

Riduci (semplifica) le frazioni ordinarie matematiche ai minimi termini: misure e di esempi