5. Come generare
numeri primi

 

 

 

In questo paragrafo cominciamo a rispondere alle domande poste alla fine del paragrafo precedente, e precisamente cominciamo dal problema di determinare tutti i numeri primi nell'intervallo [1,N] dove N è un intero “grande”. Un metodo possibile è quello di scorrere la lista di tutti questi interi, e verificarne singolarmente l'eventuale primalità: Eratostene scoprì che questa procedura è estremamente dispersiva, nel senso che gran parte del calcolo è inutilmente ripetuta più volte, e quindi suggerì una strategia alternativa che risulta di gran lunga più efficiente.
Discuteremo questo aspetto quantitativo nell'Appendice A.2 .


Figura 3:
Il crivello di Eratostene. Il meccanismo di funzionamento è tutto sommato piuttosto semplice: saltato il numero 1, che è speciale come abbiamo spiegato nel § 2.1 , si prende il primo numero che soddisfa la Definizione 2.1 , e cioè 2, lo si evidenzia mettendolo dentro un cerchio e se ne eliminano tutti i multipli fino al limite desiderato N , in questo caso 225. Si cerca quindi l'intero successivo non ancora cancellato, che è 3, lo si evidenzia e si eliminano tutti i suoi multipli. Si ripete la stessa procedura per tutti i numeri primi fino a N1/2: ciò che resta sono il numero 1 e tutti i numeri primi nell'intervallo [2, N] . Le linee colorate “cancellano” i multipli dei numeri primi 2,3,5,7,11 e 13.

 

La procedura di Eratostene è nota con il nome di “crivello” (che vuol dire “setaccio”): si passano i numeri interi positivi attraverso un opportuno setaccio, e quelli che restano sono solo i numeri primi. La Figura 3 illustra il Crivello di Eratostene applicato all'intervallo [1,225]. È relativamente semplice spiegare il procedimento in forma algoritmica: supponiamo di voler eseguire il crivello sugli interi nell'intervallo [1,N] , dove N è un parametro a nostra scelta.

 

IL CRIVELLO DI ERATOSTENE, VERSIONE DI BASE

1 function crivello(N)
2 boolean c[N]={vero*N }
3 int
p←2
4 while( p2≤N )
5 int n←p2
6 while ( n≤N )
7 c[n]←falso
8 n←p+n
9 endwhile
10 repeat
11 p←p+1
12 until (c[p]=vero)
13 endwhile

Figura 4: Lo pseudo-codice per il Crivello di Eratostene.

 

1. Si scrivono tutti gli interi da 1 ad N .

2. Si parte da p=2 (il più piccolo numero primo).

3. Si cancellano tutti i multipli di p partendo da p2 fino ad N .

4. Si cerca il più piccolo intero q>p non ancora cancellato. Se q2>N la procedura termina.

5. Si pone p=q e si torna al passo 3 .

Si noti che l'operazione di cancellazione di cui al punto 3 può essere effettuata in modo estremamente efficiente (ed è esattamente qui l'essenza dell'algoritmo) partendo da p2 ed aggiungendo sempre p all'ultimo valore trovato, fino a superare N . Infatti i multipli di p fra 2 p e p2-p , estremi inclusi, sono stati cancellati tutti nei passi precedenti, poiché hanno almeno un fattore primo<p . Si veda anche la Figura 4 .

Pierre de Fermat

A questo punto il nostro obiettivo è dimostrare che i numeri “sopravvissuti” a questa operazione sono il numero 1 e tutti i numeri primi fino ad N . Il numero 1, evidentemente, non è stato mai cancellato (il più piccolo numero cancellato è 4, alla prima iterazione). I numeri primi nell'intervallo [1, N1/2] non sono stati cancellati, perché il più piccolo multiplo del primo p che è effettivamente cancellato è 2 p , e i numeri primi nell'intervallo [N1/2,N] non sono stati cancellati perché non hanno divisori fra i numeri con i quali abbiamo effettuato le cancellazioni.


Infine, tutti i numeri composti nell'intervallo [1,N] sono stati cancellati: infatti, sia n≤N un numero composto. Dunque esistono interi a, b con 1<a≤b< n e tali che n=ab . Se a e b fossero entrambi > N1/2, il loro prodotto n dovrebbe essere a sua volta > N . Dunque n è divisibile per almeno un numero primo≤N1/2 (ogni fattore primo di a va bene), e di conseguenza è stato eliminato.
Invitiamo i Lettori a convincersi della correttezza dell'algoritmo eseguendo materialmente queste operazioni sui numeri da 1 a 100: conviene prima disporre i numeri in uno schema quadrato come nella Figura 3 . Si noterà come i multipli di 2, 3, 5, 7 compaiono lungo opportuni segmenti.

Questo è lo schema di base: naturalmente, quando si esegue questa procedura al computer, non è necessario “scrivere” esplicitamente gli interi fra 1 ed N , e sono anche possibili alcuni miglioramenti che ora andiamo a discutere. Questo schema può essere scritto in “pseudo-codice” (cioè in una forma intermedia fra il linguaggio naturale ed un linguaggio di programmazione vero e proprio) e proponiamo la nostra versione nella Figura 4 . Le istruzioni nelle righe 6–9 realizzano la fase di “cancellazione” mentre le righe 10–12 eseguono la ricerca del primo intero non cancellato successivo a p .

Se intendiamo scrivere una procedura per computer che esegua il Crivello di Eratostene, dobbiamo cominciare con l'assegnare un certo spazio di memoria per rappresentare i numeri dell'intervallo [1,N] : normalmente questo viene realizzato creando un array (cioè una matrice ad una dimensione, altrimenti detto vettore) con N posizioni. Dato che quello che ci interessa è sapere se il numero intero corrispondente alla k-esima posizione di questo array è primo oppure no, questo array conterrà inizialmente il valore vero in tutte le sue N posizioni (si veda la riga 2), e l'operazione di cancellazione descritta nel passo 3 corrisponderà a trasformare questo valore in falso (riga 7). In linguaggio più tecnico, abbiamo un array di variabili logiche (dette anche booleani), e possiamo pensare che il valore vero corrisponda, alla fine del calcolo, ai numeri primi ed al numero 1.

La prima cosa che si nota è che c'è un certo “spreco”: infatti, tutte le posizioni dell'array corrispondenti ad interi pari≥4 contengono numeri che certamente non sono primi, e quindi stiamo sprecando metà circa dell'array per contenere informazioni inutili, e per sovrammercato stiamo anche sprecando del tempo per ottenere queste stesse informazioni!
Dunque, cerchiamo un modo per sfruttare questo fatto, ed utilizzare la metà circa delle posizioni necessarie seguendo alla lettera la “ricetta” data qui sopra.
Tutto si basa sul Lemma seguente, che è la generalizzazione dell'osservazione, in sé piuttosto banale, che tutti i numeri primi, a parte il numero 2, sono dispari.

Lemma 5.1 Sia M≥1 un numero intero. Se p è un numero primo, allora p|M oppure (p,M)=1.


Leonhard Eulero

La prima modifica che possiamo apportare allo schema dato sopra è questa: se abbiamo N posizioni dell'array, invece di far corrispondere la k-esima posizione al numero k (dove k assume i valori 1, 2, 3, . . . N ), la facciamo corrispondere al numero 2k-1. Questo significa che utilizzando N posizioni, siamo in grado di eseguire il Crivello sugli interi da 1 a 2N-1, oppure, che possiamo eseguire il crivello sugli interi da 1 ad N utilizzando circa N/2 posizioni. In entrambi i casi, abbiamo un risparmio del 50% circa.

Dobbiamo subito notare che il passo 2 deve essere sostituito da “Si parte da p=3” (in un certo senso, il passo con p=2 è implicito nella nostra costruzione), che l'operazione di cancellazione dei multipli di p deve tener conto del fatto che p2 (il primo intero da cancellare) corrisponde alla posizione (p2+1)/2 , e che non vi sono multipli pari da cancellare, ma solo quelli dispari. Questo comporta una certa complicazione nei dettagli della realizzazione pratica, che qui omettiamo.

Il discorso appena fatto si riferisce al caso M=2 del Lemma 5.1 , ma vi sono valori più grandi di M per cui il rapporto tra risparmio e complicazione nei dettagli rimane vantaggioso. Ne descriviamo uno particolarmente interessante.
Se scegliamo M=30 nel Lemma 5.1 , tutti i numeri primi, a parte 2, 3, 5, non hanno fattori comuni con 30, e quindi giacciono in una delle progressioni aritmetiche 1+30k, 7+30k, 11+30k, 13+30k, 17+30k, 19+30k, 23+30k, 29+30k. La cosa interessante dal punto di vista “informatico” è che il numero di queste progressioni è 8, e quindi possiamo pensare di associare ogni intervallo di 30 interi consecutivi ad un byte, (diciamo che associamo l'intervallo di estremi 30 k e 30(k+1) al k -esimo byte per kN), e associamo il j -esimo bit del byte in questione all'intero aj+30k , dove gli aj , in ordine, valgono 1, 7, 11, 13, 17, 19, 23, 29, quando j va da 0 a 7. In questo modo non c'è “spreco” e si usano i singoli bit, con la convenzione che vero corrisponde al valore 1 e falso al valore 0.
Ovviamente il numero 30 non è speciale, ed è possibile usare, per esempio, N=210, nel quale caso vi sono 48 progressioni da esaminare e la faccenda diventa più complicata.

Come osservazione finale, notiamo che sostanzialmente la stessa procedura funziona se si vogliono determinare i numeri primi nell'intevallo [M,M+N], dove M è un intero grande. C'è una certa complicazione nel dettaglio, dovuta al fatto che il primo intero da eliminare non è necessariamente p2 come nel nostro schema, ma l'idea di base rimane la stessa.

Questa osservazione ha rilevanza pratica: se si vuole determinare un numero primo “grande” p , diciamo dell'ordine di grandezza di M , si sceglie N dell'ordine di grandezza di 2logM (in modo che vi sia una ragionevole speranza che l'intervallo [M,M+N] contenga almeno un numero primo, come spiega l'argomentazione nel § 4), e si opera un crivello con tutti i numeri primi relativamente piccoli. Evidentemente, questo non garantisce che i numeri sopravvissuti al crivello siano effettivamente primi, ma in questo modo si eliminano dall'intervallo in questione, in modo molto efficiente, tutti i numeri che non hanno alcuna speranza di essere primi. A questo punto, si sottopongono i numeri rimasti, che sono relativamente pochi, a dei test di primalità (che descriveremo nella seconda parte), che sono più onerosi dal punto di vista computazionale.
In definitiva, il vantaggio risiede nel fatto che la stragrande maggioranza degli interi vengono eliminati con un basso “costo unitario” e i pochi interi residui possono essere attaccati singolarmente, ad un costo individuale maggiore.