Test di primalità fino a sqrt(n)
Verificare in modo efficiente un singolo numero
Test di primalità fino a sqrt(n) è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 2 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.
La domanda sui numeri primi
Una competenza matematica fondamentale consiste nel determinare se un singolo numero è primo. Un numero primo ha esattamente due divisori: uno e sé stesso. Lo verifichi rapidamente. 🔍
Il controllo ingenuo
Potrebbe provare a dividere n per ogni numero da 2 fino a n meno 1. È corretto, ma terribilmente lento quando n è grande.
Il trucco della radice quadrata
Ecco l'intuizione fondamentale: è sufficiente verificare i divisori fino alla radice quadrata di n. Oltre quel limite non può comparire alcun nuovo fattore.
Perché basta la radice quadrata
I divisori compaiono in coppie il cui prodotto è n. Se fossero entrambi superiori alla radice quadrata, il loro prodotto supererebbe n, il che è impossibile.
Il limite del ciclo
Iteri i a partire da 2 finché i volte i rimane minore o uguale a n. Usare i*i evita gli errori in virgola mobile di sqrt con gli interi grandi.
while i * i <= n:
...Gestire i casi piccoli
I numeri inferiori a 2 non sono mai primi, quindi li rifiuti subito. Questo controllo mantiene il ciclo principale semplice e corretto.
if n < 2:
return FalseLa funzione completa
Metta tutto insieme: gestisca i valori piccoli, poi analizzi i possibili divisori fino alla radice. Qualsiasi divisione esatta significa che n è composto.
def is_prime(n):
if n < 2:
return False
i = 2
while i * i <= n:
if n % i == 0:
return False
i += 1
return TrueVelocizzare il controllo
Controlli 2 separatamente, poi verifichi solo i numeri dispari. Saltare i numeri pari dimezza circa il lavoro senza aggiungere complessità.
if n % 2 == 0:
return n == 2Il costo in termini di tempo
Questo test richiede un tempo O(sqrt n). Per un singolo numero fino a un miliardo si tratta di appena circa 30.000 operazioni semplici.
Un numero, non molti
Il test con la radice quadrata è ideale per una o poche richieste. Se deve verificare la primalità di un intero intervallo, un crivello sarà molto più veloce.
Evitare il problema della radice quadrata
Confrontare con i*i invece di math.sqrt evita gli errori di arrotondamento che potrebbero far accettare o rifiutare erroneamente numeri al limite.
Verifica rapida
Confermi il limite che rende veloce questo test.
Riepilogo
Ora può verificare se un numero è primo in tempo O(sqrt n), gestire i valori piccoli, saltare i numeri pari e usare i*i per mantenere l'esattezza. ✅
Domande Frequenti
La lezione «Test di primalità fino a sqrt(n)» è gratuita?
Sì — il testo completo di «Test di primalità fino a sqrt(n)» è 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 «Test di primalità fino a sqrt(n)»?
Verificare in modo efficiente un singolo numero 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 2 di 4.
Quanto tempo richiede la lezione «Test di primalità fino a sqrt(n)»?
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