Numeri primi in Python

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

7 – Primi esercizi in Python

8 – Errori in Python

9 – Script Python

10 – Scambio di variabili

Leave a Reply