Il Crivello di Eratostene è l'algoritmo più antico e famoso utilizzato per la ricerca dei numeri primi.
L'algoritmo ha l'obbiettivo di estrarre tutti i numeri primi da un insieme ordinato di valori che vanno da 2 a n (lettera che rappresenta un valore generico per definire la fine dell'intervallo di interesse). Per la realizzazione del Crivello di Eratostene in Python implementeremo una funzione alla quale passeremo come parametro una lista ordinata di numeri di lunghezza arbitraria.
Definiamo adesso la funzione e inizializziamo una lista vuota nella quale inseriremo tutti i numeri primi trovati:
Innestiamo un ciclo for che ci consentirà di verificare se ogni numero alla i-esima posizione è primo. Nel caso dell'algoritmo in questione: un elemento è primo, e quindi valido, se il suo valore non è "False". Dunque troviamo il primo elemento valido e poniamo in False i relativi multipli innestando un secondo ciclo for.
Adesso non ci resta che estrarre tutti i numeri diversi da "False" e porli in una nuova lista. Abbiamo così concluso l'algoritmo e determinato tutti i primi presenti nella lista data.
Determiniamo ora una funzione crea_lista a cui passiamo come parametro la lunghezza desiderata e invochiamo l'algoritmo appena realizzato.
Output:
