Crivello di Eratostene
Elencare tutti i numeri primi fino a N in tempo quasi lineare
Crivello di Eratostene è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 3 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.
Numeri primi in massa
A volte servono tutti i numeri primi fino a N, non un solo controllo. Il crivello di Eratostene li trova tutti con un'unica scansione. 🧹
L'idea fondamentale
Cominci assumendo che ogni numero sia primo. Poi elimini i multipli di ogni primo trovato, lasciando solo i primi effettivi.
Impostare i flag
Crei una lista booleana in cui l'indice i indica se i è primo. Questo array è la superficie su cui il crivello opera.
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = FalseScorrere i candidati
Faccia avanzare i. La prima volta che raggiunge un numero ancora contrassegnato come True, quel numero deve essere un nuovo primo senza fattori più piccoli.
Eliminare i multipli
Per ogni primo i, contrassegni 2i, 3i, 4i e così via come non primi. Questi multipli hanno chiaramente i come divisore.
for j in range(i * i, n + 1, i):
is_prime[j] = FalseIniziare da i al quadrato
Inizi a eliminare da i*i, non da 2i. Ogni multiplo più piccolo è già stato eliminato da un primo precedente, quindi può saltarlo.
Fermarsi alla radice
È sufficiente eseguire il crivello finché i*i rimane minore o uguale a N. Oltre la radice quadrata, ogni flag True rimasto indica già un numero primo.
Il crivello completo
Combini la scansione esterna con l'eliminazione interna. Dopo il ciclo, ogni indice ancora contrassegnato come True è un primo confermato.
for i in range(2, int(n ** 0.5) + 1):
if is_prime[i]:
for j in range(i * i, n + 1, i):
is_prime[j] = FalseRaccogliere i numeri primi
Trasferisca i flag completati in una lista usando una list comprehension. Ora dispone di ogni primo fino a N, pronto per essere usato nelle richieste rapide.
primes = [i for i, p in enumerate(is_prime) if p]Perché è veloce
Il crivello richiede circa O(n log log n), un tempo quasi lineare. Ecco perché supera nettamente i controlli ripetuti sui singoli numeri.
Attenzione alla memoria
L'array dei flag usa una quantità di memoria proporzionale a N. Per limiti molto grandi, controlli il proprio budget di memoria prima di effettuare l'allocazione.
Verifica rapida
Ricordi la piccola ottimizzazione del ciclo interno.
Riepilogo
Ora può costruire un crivello per elencare tutti i numeri primi fino a N in tempo quasi lineare, iniziando ogni primo da i*i e fermandosi alla radice. ✅
Domande Frequenti
La lezione «Crivello di Eratostene» è gratuita?
Sì — il testo completo di «Crivello di Eratostene» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Crivello di Eratostene»?
Elencare tutti i numeri primi fino a N in tempo quasi lineare Eserciti Coding Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Coding Interview Prep?
Non è richiesta alcuna esperienza precedente. Coding Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 3 di 4.
Quanto tempo richiede la lezione «Crivello di Eratostene»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Coding Interview Prep?
Sì. Ogni lezione Coding Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- GCD, LCM e algoritmo euclideo
- Test di primalità fino a sqrt(n)
- Crivello di Eratostene
- Fattorizzazione prima e divisori