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.
Recuperiamo il treno coi vagoni
(ved. lezione 3),
che era sostanzialmente una lista di interi.
La lista di interi e' come il treno: aggancia
una sequenza di vagoni numerati.
Differenza tra la classe IntList e la classe Treno:
class Vagone
/* identica alla lezione 3, tranne cambiamenti estetici alla
funzione di stampa */
{
int numero;
Vagone prossimo_vagone;
Vagone(int num) /* crea il vagone isolato */
{ numero = num; prossimo_vagone = null; }
void aggancia(Vagone prossimo) { prossimo_vagone = prossimo; }
void sgancia() { prossimo_vagone = null; }
void print() /* stampa numeri separati da virgole */
{
System.out.println("" + numero);
if (prossimo_vagone!=null)
{ System.out.println(",");
prossimo_vagone.print();
}
}
}
class IntList /* ex Treno */
{
protected Vagone primo_vagone;
IntList() /* crea lista vuota, ex treno senza vagoni */
{
primo_vagone = null; // e' come il default
}
protected void aggancia(Vagone primo) { primo_vagone = primo; }
protected void sgancia() { primo_vagone = null; }
public void aggiungiInCima(int num)
{
Vagone aux = new Vagone(num);
/* creo nuovo vagone col numero */
aux.aggancia(primo_vagone);
/* aggancio il primo vagone dietro al nuovo */
aggancia(aux);
/* il nuovo diventa il primo vagone */
}
public boolean vuota() { return (primo_vagone==null); }
void print() /* stampa lista tra [] */
{
System.out.print("Lista [");
if (primo_vagone!=null) primo_vagone.print();
System.out.print("]");
}
}
Modifichiamo il crivello di Eratostene per raccogliere i numeri primi in una lista invece di stamparli.
La classe Sieve ha una lista globale (variabile di classe) in cui tutti i crivelli aggiungono i numeri primi man mano che li trovano.
static IntList primeList = new IntList();
Ogni crivello invece di scrivere il numero primo, lo inserisce
nella lista globale:
System.out.println("Numero " + i + " e' primo");
viene sostituito da:
primeList.aggiungiInCima(i);
Nella classe PNG, alla fine del main stampiamo la lista:
Sieve.primeList.print();
La lista raccoglie i numeri in ordine contrario! Il primo della lista e' l'ultimo inserito.
Per ovviare a questo inconveniente dobbiamo fare in modo che
l'aggiunta avvenga in fondo invece che in cima alla lista.
Per farlo in modo efficiente bisogna tenere un puntatore alla fine
della lista, oltre che all'inizio.
Sottoclasse lista con inserimento in fondo:
class IntList2 extends IntList
{
protected Vagone ultimo_vagone;
IntList2()
{
primo_vagone = ultimo_vagone = null; // e' come il default
}
public void aggiungiInFondo(int num)
{
Vagone aux = new Vagone(num);
/* creo nuovo vagone col numero */
if (!vuota())
{ ultimo_vagone.aggancia(aux);
/* aggancio il nuovo vagone dietro all'ultimo */
}
else
{ aggancia(aux);
/* il nuovo vagone e' il primo */
}
ultimo_vagone = aux;
/* il nuovo diventa l'ultimo vagone */
}
public void aggiungiInCima(int num)
/* re-implementata per anche gestire l'ultimo */
{
super.aggiungiInCima(num);
if (ultimo_vagone==null) ultimo_vagone = primo_vagone;
}
}
Ora nella classe Sieve definiamo primeList di classe IntList2, e i crivelli aggiungono numeri con aggiungiInFondo.