Esercizi Python per principianti

Verificare se un numero è primo in Python

In questa lezione verificherai se un numero è primo provando i divisori solo fino alla sua radice quadrata.

  • Principiante
  • 2 min di lettura
  • 1 esempio eseguibile

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.

Dai rettangoli di piastrelle al codice
number > 1🚪 Solo i numeri maggiori di 1 possono essere primi
divisor * divisor <= number🪞 Fermati al quadrato: i rettangoli dopo sono ripetizioni
number % divisor == 0🔍 Viene un rettangolo pieno: non è primo
divisor += 1➡️ Prova la larghezza successiva
Se fino alla radice quadrata non trovi divisori, il numero è primo.
In una frase

Un numero primo è un intero maggiore di 1 i cui unici divisori positivi sono 1 e sé stesso.

Punti chiave

  1. is_prime = number > 1 parte da False per 0, 1 e i numeri negativi, che non sono mai primi.
  2. while divisor * divisor <= number and is_prime: si ferma alla radice quadrata o appena trova un divisore.
  3. number % divisor == 0 significa che divisor divide esattamente il numero.
  4. 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

Esegui codice →
main.py
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}")
Crea un pulsante Run per questo esempio

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.

  1. Cambia i dati di input e prova a prevedere il risultato prima di eseguire.
  2. Aggiungi un controllo per i dati vuoti o non validi.
  3. Sposta la logica in una funzione separata e provala con diversi insiemi di dati.
Esegui nel compilatore Python →

Errori comuni

Considerare 1 un numero primo

1 ha un solo divisore, quindi non è primo. Controlla prima number > 1.

Problema
is_prime = True  # 1 would be reported as prime
Correzione
is_prime = number > 1

Ciclare fino al numero stesso

Dà la risposta giusta ma prova molti più divisori del necessario.

Problema
for divisor in range(2, number):
Correzione
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.

Tutte le sfide