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.

Quindi impostiamo la variabile div a 1 e finchè questo divisore raggiunge la metà del numero preso in input cominciamo a dividere.

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 ad 1 allora si ha solo un divisore (1) 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: ‘))

div,count=1,0

while div<=numero/2 and count<2:

if numero%div==0:

count+=1

div+=1

if count==1:

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 in python

3 – Operatori aritmetici e di assegnazione in python

4 – Stringhe in python

5 – Casting in python

6 – Input e print in python

7 – Primi esercizi in python

8 – Errori in python

9 – Script python

10 – Scambio di variabili in python

Autore dell'articolo: Cristina

Avatar per Coding Creativo

Lascia un commento

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