Verificare se un numero è primo in Python
In questa lezione verificherai se un numero è primo provando i divisori solo fino alla sua radice quadrata.
Introduzione
Il problema
I numeri primi stanno dietro la cifratura su internet, le tabelle hash e molti rompicapi. Controllare se un numero è primo provando ogni divisore fino al numero stesso funziona per 29, ma diventa lentissimo per numeri grandi. Una piccola intuizione rende il controllo molto più veloce.
Immaginalo così
Cercare i divisori è come provare a disporre delle piastrelle in un rettangolo pieno. 36 piastrelle stanno come 1×36, 2×18, 3×12, 4×9 e 6×6. Dopo il quadrato (6×6) tornano gli stessi rettangoli, solo girati, quindi oltre la radice quadrata non c'è niente di nuovo da trovare. 29 piastrelle stanno solo come 1×29, quindi 29 è primo.
number > 1🚪 Solo i numeri maggiori di 1 possono essere primidivisor * divisor <= number🪞 Fermati al quadrato: i rettangoli dopo sono ripetizioninumber % divisor == 0🔍 Viene un rettangolo pieno: non è primodivisor += 1➡️ Prova la larghezza successivaUn numero primo è un intero maggiore di 1 i cui unici divisori positivi sono 1 e sé stesso.
Punti chiave
is_prime = number > 1parte da False per 0, 1 e i numeri negativi, che non sono mai primi.while divisor * divisor <= number and is_prime:si ferma alla radice quadrata o appena trova un divisore.number % divisor == 0significa chedivisordivide esattamente il numero.- Per 29 il ciclo prova solo 2, 3, 4 e 5 prima di poter dire che il numero è primo.
Quando si usa?
- Rompicapi con i numeri ed esercizi come elencare i primi o trovare i fattori primi.
- Capire perché fermarsi prima e controllare solo fino a un limite rende i cicli più veloci.
- Validare l'input in strumenti di matematica.
Quando non serve
- Elencare tutti i primi fino a un limite grande: il crivello di Eratostene è molto più veloce che controllare ogni numero.
- Crittografia con numeri lunghi centinaia di cifre: i sistemi veri usano test probabilistici.
Codice di esempio
number = 29
is_prime = number > 1
divisor = 2
while divisor * divisor <= number and is_prime:
if number % divisor == 0:
is_prime = False
divisor += 1
print(f"{number} is prime: {is_prime}")
Risultato dell'esecuzione
29 is prime: True
Spiegazione del codice
Il ciclo deve provare i divisori solo finché divisor * divisor <= number. Il motivo è che, se n ha un divisore maggiore della sua radice quadrata, questo è accompagnato da un divisore più piccolo che il ciclo ha già controllato. Così la complessità scende a O(√n), e il risultato mostra che 29 è primo.
Modifica i valori ed esegui il programma nel compilatore Python online CodeUtility senza installare Python.
Esercizi di approfondimento
Prova a modificare il codice seguendo i suggerimenti qui sotto. Cambiare il codice e osservare il risultato ti aiuta a capire molto più che leggerlo soltanto.
- Cambia i dati di input e prova a prevedere il risultato prima di eseguire.
- Aggiungi un controllo per i dati vuoti o non validi.
- Sposta la logica in una funzione separata e provala con diversi insiemi di dati.
Errori comuni
Considerare 1 un numero primo
1 ha un solo divisore, quindi non è primo. Controlla prima number > 1.
is_prime = True # 1 would be reported as prime
is_prime = number > 1
Ciclare fino al numero stesso
Dà la risposta giusta ma prova molti più divisori del necessario.
for divisor in range(2, number):
while divisor * divisor <= number:
Hai finito questa lezione?
Segnala come imparata per tenere traccia dei tuoi progressi.
Esercitati con una sfida
Usa ciò che questa lezione spiega per risolvere un problema reale. Ogni sfida gira nel browser, con test immediati e una revisione dell'IA.
- Verifica Numero Primo Stabilisci se un numero è primo. Facile
- Massimo Fattore Primo Trova il più grande numero primo che divide un intero positivo. Media
- List Primes With a Sieve Find primes up to a limit by marking composite multiples. Media