2.5. Numeri primi Come realizzare il crivello di Eratostene, Come cercare i numeri primi. Prerequisiti operatori: //, %, <, e ==. funzioni con parametri, struttura di selezione: if ..else, struttura di iterazione: while e istruzione break, liste. Argomenti trattati crivello di Eratostene, numeri primi, ottimizzazione del codice. Problema Scrivere una funzione che restituisca una lista di numeri primi ricavata con il metodo del crivello di Eratostene. E una funzione che, partendo da una lista vuota, aggiunga man mano numeri primi. Soluzione Si fa risalire ad Eratostene, un metodo furbo per individuare i numeri primi presenti nella sequenza dei primi numeri naturali: Si scrivono i primi enne numeri naturali, Si toglie lo zero e l’uno che non sono primi Si tiene il prossimo numero ( in questo caso il 2) e si cancellano tutti i suoi multipli, Si ripete l’istruzione precedente fino ad essere arrivati in fondo. Di seguito riporto i risultati delle prime iterazioni dell’algoritmo descritto sopra.
In un linguaggio di progetto il la funzione può diventare: def crivello(n):
popola una lista con i numeri da 2 a n per ogni elemento della lista,
- se divide un elemento che lo segue
- cancella dalla lista quest’altro elemento
..restituisci la lista Per realizzare l’algoritmo ci sarà bisogno di due cicli annidati e di due indici, uno per scorrere tutti gli elementi della lista, l’altro per realizzare il confronto di questi elementi con gli altri: def crivello(n):
c=range(2, n+1) print “prima dei buchi:n”, c i=0 while i<len(c):
j=i+1 while j<len(c):
# print c[i], c[j] if c[j] % c[i] == 0: del c[j] j+=1i+=1
print “ndopo i buchi:n”, c return c
Come il solito, qualche istruzione print ben piazzata può contribuire a capire il funzionamento del codice, una volta esaurita la sua funzione, può essere commentata o cancellata. Il crivello funziona per “sottrazione”, metto tutti i numeri da 2 a enne e poi elimino i multipli, posso anche operare per “addizione”, parto da una lista vuota e aggiungo i numeri primi. Questa funzione va bene se voglio avere una lista con numeri primi inferiori ad un certo valore, ma se volessi generare la sequenza dei numeri primi dovrei procedere per addizione. In pseudocodice: def primi(massimo):
preparo un lista vuota per ogni numero da 2 al massimo:
- se è divisibile per un numero compreso tra 2 e il numero stesso:
- non è primo
- altrimenti:
- aggiungo questo numero alla lista dei numeri primi
restituisco la lista
Per tradurre questo algoritmo in Python dobbiamo predisporre alcune variabili e realizzare due cicli, uno annidato nell’altro: def primi0(massimo):
primi=[] num=1 while num<massimo:
num+=1 d=2 while d<num:
if (num % d)==0: break d+=1
- if not d<num:
- primi.append(num) print num
return primi
Quando un algoritmo contiene dei cicli annidati è buona norma dubitare che sia efficiente. Le istruzioni contenute nel ciclo più interno verranno eseguite molte volte. Nella funzione precedente per trovare i numeri primi inferiori a 200, l’operazione che calcola il resto della divisione: num % d, viene eseguita 4424 volte. C’è spazio per migliorare l’algoritmo... Intanto possiamo osservare che a parte il numero 2 tutti gli altri primi sono numeri dispari quindi, possiamo trattare 2 come caso particolare e poi cercare i primi solo tra i numeri dispari incrementando il valore di num di due invece che di uno. Chiamiamo i l’incremento. Ovviamente non occorrerà più verificare se un numero è divisibile per un numero pari, quindi anche il possibile divisore andrà incrementato di 2: def primi1(massimo):
primi=[2] i=2 print 2 num=1 while num<massimo:
num+=i d=3 while d<num:
if (num % d)==0: break d+=i
- if not d<num:
- primi.append(num) print num
return primi
Quest’altro algoritmo, nelle stesse condizioni della prova precedente, esegue 2141 volte l’istruzione: num % d. Con questi semplici cambiamenti abbiamo più che dimezzato le istruzioni eseguite dall’algoritmo. Ma si può fare di più. Nessun numero è divisibile per un valore compreso tra la metà del numero stesso e il numero stesso. Ad esempio nell’intervallo ]26; 53[ non possono esserci divisori di 53. Quindi se non ho trovato un divisore tra 3 e enne/2 non lo troverò neppure tra enne/2 e enne-1. Quindi quando il divisore supera la metà del numero, posso sospendere la ricerca. Cambia la condizione che controlla il ciclo while e cambia di conseguenza il controllo per riconoscere se un numero è primo: def primi2(massimo):
primi=[2] i=2 print 2 num=1 while num<massimo:
num+=i d=3 while d<(num//2):
if (num % d)==0: break d+=i
- if not d<(num//2):
- primi.append(num) print num
return primi
In questo modo, le operazioni più critiche (% e //) vengono eseguite 1285 volte: ancora un buon miglioramento! Ma possiamo ridurre ancora il numero dei controlli, infatti se osserviamo bene il comportamento dei numeri possiamo scoprire che se c’è un divisore maggiore della radice quadrata del numero allora deve essercene anche uno minore. Se 100 è divisibile per un numero maggiore di 10, supponiamo 25 allora deve essere divisibile anche per un numero inferiore a 10, infatti è divisibile per 100/25 che è 4. Viceversa se non abbiamo trovato divisori di enne nell’intervallo tra 3 e la radice quadrata di enne, non ce ne saranno neppure dopo. il nostro ciclo più interno può quindi fermarsi alla radice quadrata del numero invece che andare fino alla metà del numero, un altro bel risparmio di cicli. In Python, la radice quadrata non è una funzione interna, si trova nella libreria math quindi per poterla usare dobbiamo caricare la libreria con l’istruzione: import math e per eseguirla dobbiamo scrivere: math.sqrt(num). L’algoritmo diventa: def primi3(massimo):
import math primi=[2] i=2 print 2 num=1 while num<massimo:
num+=i d=3 radq=math.sqrt(num) while d<radq:
if (num % d)==0: break d+=i
- if not d<=radq:
- primi.append(num) print num
return primi
Poiché anche il calcolo della radice quadrata di un numero è un’operazione pesante, invece di farla eseguire due volte, nella condizione del ciclo while e nell’istruzione if, ho preferito utilizzare una variabile. sommando le chiamate a math.sqrt e all’operatore che calcola il resto della divisione(%), ottengo 448 istruzioni eseguite. Circa un terzo della versione precedente e un decimo di quella iniziale! Cambiando un po’ l’algoritmo si può migliorare ancora... Leggere una libreria matematica per eseguire un’operazione, non è il massimo dell’efficienza e la radice quadrata stessa è un’operazione piuttosto pesante. Python ci mette a disposizione una funzione che, dati un dividendo e un divisore, restituisce, come risultato, il quoziente e il resto della divisione.: >>> print divmod(27, 4) (6, 3) perché 27 equivale a 6*4+3. divmod() è una funzione molto efficiente e possiamo utilizzarla nel nostro algoritmo. Dall’osservazione che se divido enne per un numero inferiore alla sua radice quadrata ottengo un quoziente maggiore della sua radice quadrata, possiamo trasformare il ciclo più interno in modo che calcoli quoziente e resto della divisione tra num e d e termini in uno di questi due casi: se il resto è uguale a 0, in questo caso num non è primo, o se il divisore ha superato il quoziente, in questo caso num è primo. Per uscire da un ciclo Python mette a disposizione l’istruzione break. Quindi l’algoritmo diventa: def primi4(massimo):
primi=[2, 3] i=2 print 2 print 3 num=3 while num<massimo:
num+=i d=3 while True:
q, r = divmod(num, d) if r==0:
breakd+=i if d>q :
primi.append(num) print num breakreturn primi
Il comando while True: indica un ciclo che continua finché non viene eseguita un’istruzione break. Il numero di divisioni, chiamate alla funzione divmod() ora sono: 278, un altro notevole miglioramento. Con qualche altro trucco si può migliorare ulteriormente l’efficienza dell’algoritmo.
Riassumendo Per calcolare se un numero è divisibile per un altro si può usare l’operatore % oppure la funzione divmod()verificando che il resto sia zero. Si può terminare un ciclo usando l’istruzione break. Scrivere un programma che funziona è il primo passo, il programma deve anche essere “elegante “ ed efficiente.