Un modo più efficiente per trovare i numeri primi è quello di utilizzare l'algoritmo del crivello di Eratostene. L'idea di questo algoritmo è quella di eliminare tutti i multipli di ogni numero primo trovato, in modo che alla fine rimangano solo i numeri primi. Questo metodo riduce significativamente il tempo necessario per trovare i numeri primi.
Ecco come funziona l'algoritmo del crivello di Eratostene in pseudocodice:
- Creare una lista di numeri interi da 2 a un valore massimo specificato.
- Iniziare con il primo numero primo, che è 2.
- Eliminare tutti i multipli di 2 dalla lista.
- Passare al successivo numero primo non ancora eliminato nella lista e ripetere il passo 3.
- Continuare fino a quando tutti i numeri primi nella lista sono stati considerati.
Codice: Seleziona tutto
def crivello_eratostene(n):
# creiamo una lista di numeri da 2 a n
nums = list(range(2, n+1))
# iniziamo a cercare i multipli dei numeri nella lista
for i in nums:
# se il numero è stato già segnato come non primo, lo ignoriamo
if i == None:
continue
# segniamo tutti i multipli di i come non primi
for j in range(i*2, n+1, i):
nums[j-2] = None
# ritorniamo solo i numeri che non sono stati segnati come non primi
return [x for x in nums if x is not None]La funzione crea una lista di n numeri interi e inizializza tutti i numeri come numeri primi. Poi, inizia a esaminare i numeri nella lista, iniziando con 2. Se il numero è ancora segnato come primo, viene aggiunto alla lista dei numeri primi. Quindi, tutti i multipli del numero sono contrassegnati come non primi nella lista. La funzione continua a esaminare i numeri nella lista in ordine crescente, saltando quelli già contrassegnati come non primi, finché tutti i numeri primi sono stati trovati.
Ecco un esempio di come usare la funzione eratostene_sieve per trovare i numeri primi fino a 100:
Codice: Seleziona tutto
num_primi= crivello_eratostene(100)
print(num_primi)
Certo, ecco una forma semplice e ben leggibile del crivello di Eratostene:
Ecco una tabella dei numeri primi da 1 a 50, più colorata e bella del mio esempio, che spero possa rendere meglio l'idea del processo di semplificazione per ottenere i numeri primi.