Il crivello di Eratostene: l'algoritmo viene utilizzato per trovare (identificare) i numeri primi in una lista. Suggerimento: inizia eliminando i multipli dei numeri primi più piccoli

Il matematico greco Eratòstene di Cirene (275 - 194 aC) utilizzò un metodo nuovo e semplice per determinare se i numeri in una lista sono primi o meno.
Iniziò con i noti piccoli numeri primi 2, 3, 5, 7, 11, 13, 17, 23, ecc. È chiaro che tutti i loro multipli non sono numeri primi ma composti.

Dispose un elenco di numeri naturali in ordine crescente. Quindi ha identificato e rimosso tutti i numeri composti più grandi in questo elenco poiché sono multipli dei numeri primi più piccoli e quindi ha separato i numeri primi più grandi in questo elenco.
Illustriamo questo metodo di seguito, con un elenco di numeri ordinati in ordine crescente, da 2 a 100:

Il numero 2 è un numero primo, quindi identifichiamo prima tutti i multipli di 2 nella lista:
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
... e così via, fino al numero: 2 × 50 = 100.
Il numero 2 × 51 = 102, è maggiore di 100, quindi possiamo fermarci.
Rimuovi tutti i multipli del numero 2 dall'elenco: 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.

Il numero 3 è un numero primo, quindi identifichiamo prima tutti i multipli di 3 nella lista:
3 × 2 = 6 (Questo numero è già stato rimosso dall'elenco, è un multiplo di 2);
3 × 3 = 9
3 × 4 = 12 (Questo numero è già stato rimosso dall'elenco, è un multiplo di 2);
3 × 5 = 15
3 × 6 = 18 (Questo numero è già stato rimosso dall'elenco, è un multiplo di 2);
... e così via, fino al numero: 3 × 33 = 99.
Il numero 3 × 34 = 102, è maggiore di 100, quindi possiamo fermarci..
Rimuovi tutti i multipli del numero 3 dall'elenco: 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.
Se abbiamo già rimosso tutti i multipli del numero 2 dall'elenco, dobbiamo solo rimuovere questi numeri: 9, 15, 21, 27, 33, 39, 45, 51, 57, 63, 69, 75, 81, 87, 93. 99. Questi numeri sono dettagliati di seguito, scritti come multipli del numero 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.

Procediamo quindi con il seguente numero primo, 5:
5 × 2 = 10 (Questo numero è già stato rimosso dall'elenco: è un multiplo di 2);
5 × 3 = 15 (Questo numero è già stato rimosso dall'elenco: è un multiplo di 3);
5 × 4 = 20 (Questo numero è già stato rimosso dall'elenco: è un multiplo di 2);
5 × 5 = 25
5 × 6 = 30 (Questo numero è già stato rimosso dall'elenco: è un multiplo di 2 e 3);
5 × 7 = 35
... e così via, fino al numero: 5 × 20 = 100 (Questo numero è già stato rimosso dall'elenco: è un multiplo di 2).
Il numero 5 × 21 = 105, è maggiore di 100, quindi possiamo fermarci..
Rimuovi tutti i multipli del numero 5 dall'elenco: 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85, 90, 95, 100.
Se non ci prendiamo cura dei multipli di 2 e 3, che sono già stati rimossi dall'elenco, ci rimangono ancora questi numeri da rimuovere: 25, 35, 55, 65, 85, 95, es. esattamente quei numeri che hanno nella loro scomposizione in fattori primi solo fattori 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 ripetiamo il processo con il prossimo numero primo 7:
7 × 2 = 14 (il numero è già stato rimosso dall'elenco - è un multiplo di 2);
7 × 3 = 21 (il numero è già stato rimosso dall'elenco - è un multiplo di 3);
7 × 4 = 28 (il numero è già stato rimosso dall'elenco - è un multiplo di 2);
7 × 5 = 35 (il numero è già stato rimosso dall'elenco - è un multiplo di 5);
7 × 6 = 42 (il numero è già stato rimosso dall'elenco - è un multiplo di 2 e 3);
7 × 7 = 49
... e così via, fino al numero: 7 × 14 = 98 (il numero è già stato rimosso dall'elenco - è un multiplo di 2).
7 × 15 = 105, è maggiore di 100, quindi possiamo fermarci..
Rimuovi tutti i multipli del numero 7 dall'elenco: 14, 21, 28, 35, 42, 49, 56, 63, 70, 77, 84, 91, 98.
Se non ci prendiamo cura dei multipli di 2, 3 e 5, che sono già stati rimossi dall'elenco, dobbiamo comunque rimuovere: 49, 77, 91. Questi sono proprio i numeri che hanno nella loro scomposizione in fattori primi solo fattori primi maggiori o uguali a 7:
7 × 7 = 49
7 × 11 = 77
7 × 13 = 91.

Il prossimo numero primo nell'elenco è 11 e dovremmo rimuovere i multipli di 11 dall'elenco.
Tuttavia, come abbiamo visto nei passaggi precedenti, dovremmo solo tentare di rimuovere dall'elenco i numeri che hanno nella loro fattorizzazione in numeri primi fattori maggiori o uguali a 11.
Ma abbiamo già 11 × 11 = 121, che è maggiore di 100.
Ciò significa che tutti i numeri rimasti nell'elenco dopo aver eseguito i passaggi precedenti sono già numeri primi.

L'elenco dei numeri primi è costituito dai numeri non rimossi.
Dopo aver rimosso dalla lista tutti i multipli dei numeri primi 2, 3, 5 e 7, rimaniamo nella lista con questi numeri: 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 - l'elenco dei numeri primi da 2 a 100.

Alcuni articoli sui numeri primi