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.

Descrizione dell’algoritmo:

1. Dato in input un numero, verifichiamo che sia maggiore di 1. Se non lo è, visualizziamo un messaggio di errore poiché i numeri primi sono definiti solo per numeri maggiori di 1.
2. Iniziamo con l’impostare una variabile div a 2 e una variabile count a 0. div è il divisore con cui verificheremo se il numero è primo, mentre count tiene traccia del numero di divisori trovati.
3. Utilizziamo un ciclo while che continua finché div è minore o uguale alla metà del numero e count è uguale a 0. Questo ci permette di ottimizzare l’algoritmo evitando di dividere inutilmente numeri molto grandi.
4. All’interno del ciclo, controlliamo se il numero è divisibile per div usando l’operatore modulo (%). Se il resto della divisione è zero, incrementiamo count poiché abbiamo trovato un divisore.
5. Dopo ogni iterazione, incrementiamo div di uno.
6. Se alla fine del ciclo count è ancora zero, il numero è primo. Altrimenti, non è primo.

Video Tutorial Gratuiti su Python: vai al canale per trovare la playlist dedicata

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!')

Con questo algoritmo, siamo in grado di determinare se un numero inserito dall’utente è primo o meno.

Miglioramenti e ottimizzazioni algoritmo sui numeri primi in Python

Potremmo fare alcune ottimizzazioni all’algoritmo precedentemente proposto. In particolare possimo evidenziare questo miglioramenti e ottimizzazioni:

1. Verifica dei numeri pari: Possiamo ottimizzare ulteriormente l’algoritmo evitando di controllare i divisori per i numeri pari, ad eccezione di 2. Se il numero è pari diverso da 2, sappiamo già che non è primo perché è divisibile per 2.
2. Ottimizzazione della ricerca dei divisori: Possiamo limitare la ricerca dei divisori fino alla radice quadrata del numero anziché fino alla sua metà. Questo perché se un numero ha un divisore maggiore della sua radice quadrata, avrà anche un divisore minore della sua radice quadrata.
3. Refactoring del codice: Possiamo migliorare leggibilità e chiarezza del codice suddividendo le responsabilità in funzioni più piccole e descrivendo chiaramente l’intento di ciascuna parte dell’algoritmo.
4. Gestione degli input non validi: Possiamo aggiungere controlli aggiuntivi per gestire input non validi, ad esempio se l’utente inserisce caratteri non numerici anziché numeri.

Ecco un esempio di implementazione con ottimizzazioni:

import math

def is_prime(numero):
    if numero <= 1:
        return False
    elif numero == 2:
        return True
    elif numero % 2 == 0:
        return False
    else:
        limite = int(math.sqrt(numero)) + 1
        for div in range(3, limite, 2):
            if numero % div == 0:
                return False
        return True

numero = int(input('Inserire un numero: '))

if is_prime(numero):
    print('Numero primo!')
else:
    print('Il numero non è primo!')

Nella funzione is_prime, sono state apportate diverse ottimizzazioni per migliorare l’efficienza e la chiarezza dell’algoritmo per determinare se un numero è primo:

1. Controllo se il numero è minore o uguale a 1: Il primo controllo verifica se il numero è minore o uguale a 1. In tal caso, restituisce False poiché i numeri primi sono definiti come numeri naturali maggiori di 1.
2. Controllo se il numero è uguale a 2: Successivamente, controlla se il numero è uguale a 2. Se sì, restituisce True perché 2 è il primo numero primo.
3. Controllo se il numero è pari: Se il numero è pari diverso da 2, viene restituito False poiché i numeri pari (ad eccezione del 2) non possono essere primi.
4. Calcolo del limite della ricerca dei divisori: Per ottimizzare la ricerca dei divisori, il limite viene calcolato come la radice quadrata del numero (math.sqrt(numero)), arrotondata per eccesso e incrementata di 1. Questo perché se un numero ha un divisore maggiore della sua radice quadrata, avrà anche un divisore minore della sua radice quadrata.
5. Iterazione sui divisori dispari: Il ciclo for itera sui divisori dispari a partire da 3 fino al limite calcolato, incrementando di 2 ad ogni passaggio. Questo perché abbiamo già escluso i numeri pari diversi da 2 come potenziali divisori.
6. Controllo dei divisori: Durante l’iterazione, viene controllato se il numero è divisibile per il divisore corrente. Se sì, viene restituito False poiché il numero non è primo.
7. Restituzione del risultato: Se il ciclo termina senza trovare divisori, il numero è primo e viene restituito True.

Queste ottimizzazioni riducono il numero di iterazioni necessarie per determinare se un numero è primo, rendendo l’algoritmo più efficiente e veloce, soprattutto per numeri grandi.

Se stai pensando di iscriverti ad un corso in diretta su Python, ecco alcuni suggerimenti per esplorare al meglio questa opportunità:

1. Apprendimento Interattivo: I corsi in diretta offrono un’esperienza di apprendimento interattiva, che ti permette di interagire direttamente con l’istruttore e gli altri partecipanti. Questo può favorire un apprendimento più rapido e approfondito.
2. Guida Esperta: I corsi in diretta sono condotti da istruttori esperti che possono guidarti attraverso i concetti chiave e rispondere alle tue domande in tempo reale. Questo ti permette di ottenere una comprensione più approfondita dei concetti e delle best practices di programmazione Python.
3. Feedback Personalizzato: Durante il corso, avrai l’opportunità di ricevere feedback personalizzato sull’avanzamento del tuo apprendimento e sui tuoi progetti. Questo può aiutarti a identificare e superare le tue sfide specifiche di apprendimento.
4. Networking: Partecipare ad un corso in diretta ti offre l’opportunità di connetterti con altri studenti e professionisti del settore. Questo può portare a collaborazioni future, opportunità di mentoring e sviluppo di una rete professionale preziosa.
5. Progetti Pratici: I corsi in diretta spesso includono progetti pratici che ti consentono di applicare ciò che hai imparato in situazioni reali. Questi progetti ti aiutano a sviluppare competenze pratiche e a costruire un portfolio di lavoro.
6. Aggiornamenti Continui: Python è un linguaggio di programmazione in continua evoluzione. Partecipare ad un corso in diretta ti consente di rimanere aggiornato sulle ultime novità del linguaggio e sulle best practices di sviluppo.

Ancora indeciso? Contattaci per maggiori informazioni: info@insegnarecoding.com

Alcuni link utili

Corso in diretta su Python

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