La parola della settimana: CRIVELLO DI ERATOSTENE

crivello di Eratostene 

(Parole crociate senza schema 800130)

Il crivello (o setaccio) di Eratostene è un antico algoritmo utilizzato per trovare tutti i numeri primi in una sequenza data di numeri naturali. Prende il nome dal matematico greco Eratostene di Cirene, a cui è attribuita la sua invenzione. L'algoritmo, noto per la sua semplicità ed efficienza nel calcolo dei numeri primi, è uno strumento fondamentale nella teoria dei numeri.

Il termine "crivello" o "setaccio"  [gr. κόσκινον (kóskinon)] è una metafora che trae origine dal comune strumento da cucina utilizzato per separare gli elementi desiderati dal materiale indesiderato o per setacciare la farina per rimuovere i grumi. Nel contesto del setaccio di Eratostene, il processo "setaccia" metaforicamente una lista di numeri interi e separa i numeri primi dai numeri che primi non sono.

Proprio come un setaccio fisico permette alle particelle più piccole di passare attraverso le sue maglie trattenendo quelle più grandi, il setaccio di Eratostene permette ai numeri primi di "passare" identificando e rimuovendo (o contrassegnando come non primi) i multipli di ciascun numero primo. L'algoritmo filtra in modo iterativo i multipli dei numeri primi, lasciando solo i numeri primi nell'intervallo compreso tra 2 e il limite superiore specificato, 

L'immagine del crivello o setaccio cattura efficacemente l'essenza del funzionamento dell'algoritmo: eliminare sistematicamente i numeri non primi (il materiale indesiderato) e mantenere i numeri primi (gli elementi desiderati), fornendo così una comprensione chiara e intuitiva del processo coinvolto. 

A grandi linee, l'algoritmo funziona come segue:

1) Si inizia definendo una sequenza di numeri naturali, da 2 al numero n di cui si desidera verificare la primalità.

2) Il primo numero primo è 2.

3) Si eliminano dall'elenco tutti i multipli di 2. Questi non sono primi perché hanno almeno un divisore diverso da 1 e da se stessi.

4) Si considera il numero successivo che non è stato eliminato. Questo è un numero primo perché non è stato contrassegnato come multiplo di un numero primo precedente.

5) Si ripete il processo di eliminazione dei multipli e di passaggio al numero successivo non eliminato fino a quando non si sono elaborati tutti i numeri fino a $\sqrt{n}$.

Animazione che visualizza l'algoritmo del crivello di Eratostene.

Autore: SKopp, Wikipedia Germania

I numeri che non sono stati via via eliminati dalla sequenza sono numeri primi.

Il motivo per cui è sufficiente iterare solo fino a $\sqrt{n}$ è che ogni numero non primo n deve avere almeno un fattore minore o uguale a $\sqrt{n}$. Pertanto, se un numero è primo, sarà identificato a questo punto del processo.

Il crivello di Eratostene è uno strumento efficiente per trovare tutti i numeri primi fino a circa 10 milioni. È meno efficiente per determinare la primalità di un numero dato o per elaborare sequenze di numeri molto lunghe.

A questo riguardo, sono stati sviluppati diversi metodi di ottimizzazioni del crivello di Eratostene al fine di migliorarne la velocità e ridurre la memoria necessaria ai computer utilizzati per il calcolo.

Malgrado i suoi limiti, il crivello di Eratostene resta comunque un metodo comune e potente per generare numeri primi grazie alla sua semplicità ed efficacia, soprattutto a scopo didattico e negli algoritmi applicativi in cui è necessario identificare i numeri primi entro limiti maneggiabili.