libri-javascript-python

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.

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:

….

Disponibile il libro su Python “50 Algoritmi per imparare Python”

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.

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

Disponibile il libro su Python “50 Algoritmi per imparare Python”

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