Numeri primi in Python

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

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *