
Realizziamo un programma sui numeri primi in Python utilizzando le strutture iterative studiate finora, al fine di approfondirle.
Ricordiamo dunque la definizione di numero primo:
Un numero è primo quando ha solo due divisori: uno e se stesso.
Quindi è primo ciascun numero naturale maggiore di 1 che sia divisibile solamente per 1 e per sé stesso.
La successione dei numeri primi comincia con 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, …
Algoritmo per i numeri primi in Python
Abbiamo già realizzato questo algoritmo in linguaggio C: numero primo in C. Inoltre, anche con Algobuild, abbiamo affrontato lo stesso argomento: numeri primi da 1 a 100 con Algobuild e con Scratch: numeri primi da 1 a 100 con Scratch.
Dato in input un numero verificare che sia primo.
Per realizzare questo algoritmo sui numeri primi in Python, prendiamo in input un numero e lo dividiamo a mano a mano per numeri minori della sua metà. Difatti è scontato che dividendo un numero per valori maggiori della sua metà, il resto della divisione sia diverso da 0.
Inoltre, dato che tutti i numeri sono divisibili per 1, facciamo senza anche a contarlo come divisore.
Quindi impostiamo la variabile div a 2 e la incrementiamo di volta in volta fino ad arrivare a numero/2.
Se il resto della divisione numero%div è uguale a zero, allora conteggiamo i divisori in una variabile contatore count inizializzata a zero.
Se la variabile count rimane a 0 allora non si trovano divisori e quindi il numero è primo. In caso contrario il numero non è primo.
Ottimizziamo l’algoritmo terminando il ciclo se il divisore raggiunge la metà del numero preso in considerazione ma anche se il contatore diventa 1, così da non dividere inutilmente e risparmiare molto più tempo. Ciò è indicato soprattutto per numeri molto grandi.
Ecco dunque il codice completo:
numero=int(input(‘Inserire un numero: ‘))
if numero<=1:
print(‘Devi inserire un numero maggiore di 1’)
else:
div,count=2,0
while div<=numero/2 and count==0:
if numero%div==0:
count+=1
div+=1
if count==0:
print(‘Numero primo!’)
else:
print(‘Il numero non è primo!’)
Torneremo nuovamente sui numeri primi in Python nelle prossime lezioni.
Alcuni link utili
Indice tutorial sul linguaggio Python
1 – Introduzione al linguaggio Python
2 – Le variabili
3 – Operatori aritmetici e di assegnazione
4 – Stringhe
5 – Casting
6 – Input e print
8 – Errori in Python
9 – Script Python
10 – Scambio di variabili