Numeri primi da 2 fino ad N, algortimo numeri primi

Scrivere un programma in Python che, determini i numeri primi da 2 fino ad N.

Procedimento algoritmo numeri primi da 2 fino ad N

Cominciamo a ragionare su una possibile soluzione.

Dato che è un problema complesso possiamo suddividerlo in sotto-problemi per riuscire a trovare meglio la soluzione.

Primo passo – determinare un numero primo

Per trovare un numero primo basta dividerlo per i numeri inferiori ad esso e contare i divisori. Se sono solo due, cioè 1 e se stesso, allora il numero è primo, altrimenti non lo è.

Ma possiamo fare a meno di dividere per un numero più grande della sua metà, in quanto è scontato che darà sempre un numero con la virgola.

Inoltre è scontato con un numero è divisibile quindi possiamo partire a dividere dal numero 2.

Banner Pubblicitario

Utilizziamo allora la variabili div che serve per il divisore inizializzata a 2. Div viene poi incrementata di uno per ogni iterazione fino ad arrivare alla metà del numero (N/2).

Utilizziamo anche la variabile count per contare il numero di divisori. Se il numero preso in input diviso div dà resto 0, la variabile count, inizializzata a zero, si incrementa.

Ecco la porzione di codice su cui abbiamo ragionato:

N = int(input("Inserisci l'intervallo N: "))

div, count = 2, 0

while div <= N // 2:
    if N % div == 0:
        count += 1
    div += 1

Ma nel caso di numeri molto grandi questa operazione richiederebbe parecchio tempo. Allora possiamo migliorare l’algoritmo facendo terminare le iterazioni non appena il count diventa 1, in quanto già con un divisore il numero non può essere primo.

Modifichiamo allora il while in questo modo:

while div <= N / 2 and count == 0:

....

Esplora il mondo della programmazione con il libro “50 Algoritmi per imparare Python” e libera la tua creatività!

Acquistalo adesso su Amazon

Seconda parte – Numeri primi da 2 fino ad N

Adesso dobbiamo visualizzare i numeri primi in un intervallo, da 2 ad N.

Se ad esempio prendiamo N=10, i numeri primi nell’intervallo sono: 2,3,5 e 7.

Banner pubblicitario

Per fare questo quindi chiediamo di prendere in input un numero N e utilizzando un altro ciclo while esterno cominciamo a controllare se N è primo. Se lo è lo stamperemo, altrimenti no. Dopo decrementiamo N fino ad arrivare a 2 quindi impostiamo la condizione N>1.
Ecco dunque il codice completo:

N = int(input("Inserisci l'intervallo N: "))

while N > 1:
    div, count = 2, 0
    
    while div <= N // 2 and count == 0:
        if N % div == 0:
            count += 1
        div += 1
    
    if count == 0:
        print(N)
    
    N -= 1

N. B. Al posto di utilizzare l’and all’interno della condizione, potrei utilizzare l’istruzione break dopo aver trovato il primo divisore. Più avanti nel tutorial vi spiegherò come si utilizza.

.....

if N % div == 0:
   count += 1
   break

Migliora le tue capacità di programmazione Python seguendo il nostro corso in diretta!

Conclusioni

Il programma proposto in questo articolo determina e stampa tutti i numeri primi nell’intervallo da 2 a N, dove N è un numero inserito dall’utente. Il procedimento segue una logica divisoria per determinare se un numero è primo e poi stampa i numeri primi trovati nell’intervallo specificato.

Ecco un riassunto delle caratteristiche principali del codice:

Input dell’Intervallo: Chiede all’utente di inserire un numero N che rappresenta l’intervallo massimo per la ricerca dei numeri primi.
Iterazione da N a 2: Utilizza un ciclo while per iterare attraverso tutti i numeri nell’intervallo da N a 2.
Verifica della Primalità: Per ogni numero nell’intervallo, controlla se è primo eseguendo un secondo ciclo while. All’interno di questo ciclo, il numero viene diviso per tutti i valori compresi tra 2 e la sua metà, e se trova un divisore, viene incrementato un contatore count.
Stampa dei Numeri Primi: Se il contatore count rimane uguale a 0, significa che il numero è primo e viene stampato.
Decremento di N: Alla fine di ogni iterazione, decrementa il valore di N per proseguire con il numero successivo nell’intervallo.

Il codice fornisce un metodo semplice ma efficace per determinare e visualizzare i numeri primi nell’intervallo specificato dall’utente. Tuttavia, è importante notare che per intervalli molto ampi, questo metodo potrebbe non essere il più efficiente in termini di tempo di esecuzione. In tal caso, potrebbero essere necessarie ottimizzazioni più avanzate.

Alcune tecniche di miglioramento potrebbero prevedere:

Utilizzo di un Algoritmo più Efficienti per Verificare la Primalità: Invece di dividere il numero per tutti i valori fino alla sua metà, si può ridurre il numero di divisioni controllando solo fino alla radice quadrata del numero. Se non ci sono divisori fino alla radice quadrata, allora il numero è primo. Questo approccio riduce significativamente il numero di divisioni necessarie.
Utilizzo di un Algoritmo del Crivello di Eratostene: Questo è un algoritmo più avanzato che determina i numeri primi fino a un certo limite utilizzando un set di regole specifiche. L’algoritmo del Crivello di Eratostene è molto efficiente per trovare i numeri primi in un ampio intervallo.