Problema: Trovare tutti i numeri primi minori di un dato numero intero k.
Ad ogni passata di setaccio ho:
Inizialmente la lista dei numeri primi trovati e' vuota, il prossimo numero primo e' 2, i candidati sono tutti i numeri da 2 a k.
Termina quando l'insieme dei candidati diventa vuoto.
L'idea e' di avere una serie di setacci coi buchi sempre piu' piccoli, attraverso i quali passiamo i nostri numeri candidati... fino ad esaurimento.
Possiamo vedere lo stesso algoritmo come catena di montaggio. In termine tecnico "pipeline" = tubatura.
Ogni operaio della catena ha in mano un setaccio con i buchi "tarati" su un certo numero (primo) p. Inizialmente solo il setaccio del primo operaio e' tarato (sappiamo che 2 e' primo, ma non sappiamo gli altri numeri primi).
Il primo numero che un operaio con il setaccio non tarato riceve, lo usa per tarare il proprio setaccio: diventa il numero di taratura p del setaccio.
Dopo di che all'operaio arrivano degli altri numeri (che hanno gia' passato i setacci relativi ai numeri primi minori di p).
Tutti i numeri che arrivano prova a dividerli per p. Se sono divisibili, li setaccia via (non sono primi).
Il primo che arriva e che non e' divisibile per p (e' il prossimo numero primo seguente p) lo passa al prossimo operaio della catena perche' questi tari il suo setaccio.
Tutti i numeri seguenti che arrivano e non sono divisibili per p li passa anche questi al prossimo operaio, che li setaccera' a sua volta.
La catena di montaggio e' dinamica: gli operai seguenti al primo vengono chiamati man mano che ci si accorge che servono.
Ogni operaio sa che cosa deve fare lui. Non ha la visione di come funziona il tutto (ma funziona lo stesso).
Classe crivello ("sieve" in inglese) ha il suo numero primo myPrime
e il puntatore al prossimo crivello next.
Il numero primo e' inizialmente 0, viene inizializzato col
primo numero che arriva.
Il prossimo crivello e' inizialmente null, viene costruito solo se
occorre. Ad esso vengono passati i numeri successivi non divisibili
per myPrime.
Il metodo filter gestisce la ricezione di un numero.
Come costruttore va bene quello di default.
class Sieve
{
int myPrime;
Sieve next;
void filter(int i)
{
if (myPrime==0)
{ myPrime = i;
System.out.println("Numero " + i + " e' primo");
}
else
{ if ((i % myPrime)==0)
System.out.println("Numero " + i + " non e' primo");
else
{
if (next==null) next = new Sieve();
next.filter(i);
}
}
}
}
Nota: si puo' evitare di stampare i non primi.
Classe PNG (generatore di numeri primi) usa una catena di crivelli per generare tutti i numeri primi minori di 100. Costruisce il primo crivello e gli passa tutti i numeri candidati nell'ordine. Il primo crivello inneschera' la catena di crivelli...
class PNG /* Prime Number Generator */
{
public static void main(String args[])
{
Sieve first = new Sieve();
int n;
for (n=2; n<100; n++) first.filter(n);
}
}
Vogliamo sapere quale crivello stampa che cosa.
Diamo ad ogni crivello un numero (etichetta) corrispondente all'ordine
in cui e' stato costruito.
Quando un crivello stampa, riporta nella stampa anche il suo numero.
Nella classe Sieve aggiungiamo:
In Sieve aggiungiamo:
static int counter = 0;
int label;
Sieve() /* nuovo costruttore */
{ myPrime = 0; // come per default
next = null; // come per default
label = ++counter; // per default sarebbe label = 0;
}
Nel metodo filter cambiamo le stampe:
System.out.println("Crivello "+ label + " dice che " + ...);
Ora i numeri primi vengono stampati. Vogliamo memorizzarli in una lista.
In realta', li abbiamo gia' in una lista!
La lista costituita dalla catena di crivelli dove il primo
crivello e' collegato al secondo, il secondo al terzo, ecc. ecc.
Quindi a partire dal primo crivello posso "leggere"
nell'ordine tutti i numeri primi contenuti nei vari crivelli.
Possiamo dunque NON stampare i numeri primi mentre filtriamo
(metodo "filter" della classe Sieve) e invece stamparli
tutti alla fine, scorrendo la catena di crivelli.
All'uscita dal ciclo nel "main" della classe PNG
abbiamo infatti una catena di crivelli dove il primo
contiene il piu' piccolo numero primo (=2) e l'ultimo contiene
il piu' grande numero primo minore di 100 (=97).
Occorre aggiungere alla classe Sieve un metodo di stampa.
Tale metodo e' simile a quello visto nella classe Vagone per
stampare il treno coi vagoni
(ved. lezione 3).
Infatti, il Vagone e il Sieve entrambi implementano
sostanzialmente una lista di interi.
In gergo si dice una lista "linkata" (cioe' "collegata")
di interi, perche' fatta di tante caselline dove ciascuna
contiene un intero ed e' collegata alla successiva.
Caratteristiche comuni alle classi Vagone e Sieve, che le qualificano come elementi base di una lista linkata di interi:
Aggiungiamo alla classe Sieve una funzione di stampa scritta in modo simile a quella della classe Vagone, cioe' "ricorsiva": ogni crivello stampa il suo numero primo e poi dice al prossimo crivello (se esiste) di stamparsi.
Come estetica della stampa, invece, decidiamo di far stampare i numeri primi tutti sulla stessa riga separati da virgole. Va a capo solo alla fine, dopo la stampa l'ultimo numero primo.
Questo frammento di codice va aggiunto nella classe Sieve:
void print() /* stampa numeri separati da virgole */
{
System.out.print("" + myPrime);
if (next!=null)
{ /* stampa la virgola separatrice */
System.out.print(",");
/* ora chiama ricorsivamente print sul prossimo crivello */
next.print();
}
else /* va a capo */
System.out.println();
}
}
Nel "main" della classe PNG, dopo la fine del ciclo, aggiungiamo la chiamata della funzione print sul primo crivello. Per come e' stata scritta la funzione print, il primo crivello si occupera' di stampare ricorsivamente tutti gli altri fino all'ultimo.
Il metodo "main" di PNG diventa dunque (sono cambiate solo le linee segnate come nuove):
public static void main(String args[])
{
Sieve first = new Sieve();
int n;
for (n=2; n<100; n++) first.filter(n);
System.out.println("I numeri primi trovati sono:"); // nuova
first.print(); // nuova
}