Crivello di Eratostene

È possibile trovare tutti i numeri primi minori di n molto più velocemente rispetto a eseguire un controllo di primalità per ciascun numero da 2 a n. Invece di verificare singolarmente ogni numero, possiamo proattivamente rimuovere dall’elenco tutti i numeri che sappiamo non saranno primi.

Per iniziare, possiamo considerare tutti i numeri da 2 a n contrassegnati come “forse primi”. Quindi rimuoviamo dall’elenco tutti i multipli di 2 e marchiamo 2 come “sicuramente primo”. Successivamente, rimuoviamo tutti i multipli di 3 e marchiamo 3 come “sicuramente primo”. In seguito saltiamo il 4, perché è già stato rimosso dall’elenco dei “forse primi” mentre processavamo il 2. Il numero successivo da considerare sarà il 5, e rimuoveremo tutti i suoi multipli. Saltiamo il 6 perché l’abbiamo già contrassegnato come non primo durante il passaggio con il 2. Possiamo continuare in questo modo fino a raggiungere n.

Simulazione del Crivello di Eratostene. Fai clic sui numeri e cerca di abilitare tutti i numeri primi, disabilitando invece tutti gli altri.

Proprietà interessanti e ottimizzazioni dell'algoritmo

Un’ottima conseguenza del rimuovere tutti i multipli di un numero primo p dall’elenco dei “forse primi” a partire dal più piccolo (2), e poi aumentare gradualmente p, è che invece di processare tutti i multipli 2·p, 3·p, 4·p, 5·p... possiamo iniziare direttamente da p·p. Infatti, tutti i multipli di p come 2·p, 3·p, 4·p, 5·p sono già stati rimossi dall’elenco dei “forse primi” durante la fase di elaborazione dei numeri 2, 3, 5, ecc. Il primo numero che non è stato ancora toccato è proprio p·p.

Quando iniziamo a processare p=3, possiamo quindi partire direttamente da 9, perché 6 era già stato rimosso durante l’elaborazione del numero 2. Analogamente, quando processiamo p=5, possiamo iniziare da 25, in quanto 10 (10 = 2·5) era stato rimosso durante l’elaborazione del numero 2, 15 (15 = 3·5) era stato rimosso durante l’elaborazione del numero 3 e infine 20 (20 = 4·5) era stato rimosso mentre processavamo il numero 2.

prime = [True] * n                    # prime[i] = True => i è un numero primo
prime[0] = prime[1] = False           # 0 e 1 non sono numeri primi

for i in range(2, n):                 # Ciclo da 2 a n
    if prime[i]:                      # se i è primo => contrassegna come non primi tutti i multipli di i
        for j in range(i * i, n, i):  # iniziamo da i * i poiché i multipli minori sono già stati segnati prima
            prime[j] = False

Sieve of Eratosthenes to find all the prime numbers smaller than n.

Simuliamo questo processo per n=100:

prime = [False, False, True, True, ..., True] di dimensione 100

i = 2 ⇒ prime[2] = True ⇒ for j in 4, 6, 8, ... 100 e contrassegna prime[j]=False

i = 3 ⇒ prime[3] = True ⇒ for j in 9, 12, ... 100 e contrassegna prime[j]=False

i = 4 ⇒ prime[4] = False

i = 5 ⇒ prime[5] = True ⇒ for j in 25, 30, ... 100 e contrassegna prime[j]=False

i = 6 ⇒ prime[6] = False

i = 7 ⇒ prime[7] = True ⇒ for j in 49, 56, ... 100 e contrassegna prime[j]=False

i = 8 ⇒ prime[8] = False

i = 9 ⇒ prime[9] = False

i = 10 ⇒ prime[10] = False

i = 11 ⇒ prime[11] = True ⇒ for j in [vuoto] e contrassegna prime[j]=False

A questo punto possiamo fermarci perché i * i supera già n. Quindi, non contrassegneremo come False nessun altro numero primo da qui in avanti. Alla fine possiamo iterare sull’elenco e stampare tutti i numeri primi minori di 100.

Questo approccio è notevolmente più veloce e richiede operazioni: un miglioramento davvero importante! Eseguire operazioni invece di fa una grande differenza. Riprendendo l’esempio dell’algoritmo che avrebbe richiesto 10 anni (3650 giorni) se avesse eseguito n operazioni, e 2 mesi (61 giorni) nel caso di operazioni, per servirebbero meno di 4 giorni!

Un’ulteriore ottimizzazione, menzionata nella simulazione, è di far variare i da 2 fino a , poiché il ciclo interno inizia da i·i e per tutti i numeri maggiori della radice quadrata di n, non contrassegneremo alcun numero con prime[j] = False nel ciclo interno (il limite superiore di questo ciclo è n).

Input

La prima riga dell’input contiene un singolo intero n (2 ≤ n ≤ ).

Output

Il programma deve stampare tutti i numeri primi minori o uguali a n.

Esempi

Ingresso	Uscita
8	2 3 5 7
17	2 3 5 7 11 13 17
19	2 3 5 7 11 13 17 19

Proprietà interessanti e ottimizzazioni dell'algoritmo

Input

Output

Esempi

Constraints

To check your solution you need to sign in

Sign in to continue