Soluzione al Laboratorio 02:

CRIVELLO DI ERATOSTENE E VARIANTI

Vedere il testo del laboratorio 02.

Vedere il'ultima parte della lezione 4 per l'algoritmo del Crivello di Eratostene in Java.

Diamo qui la soluzione all'esercizio che chiedeva:

Il numero da controllare va preso da command-line, quindi una prima modifica da apportare al main e' la seguente (in grassetto la parte modificata):

public static void main(String args)
{
  if (args.length<1)
     System.out.println("Errore: manca il parametro");
  else
  {
    int k = Integer.parseInt(args[0]);
    /* quella che segue e' la parte solita dove abbiamo fatto
       arrivare il ciclo fino a k compreso */
    Sieve first = new Sieve();
    int n;
    for (n=2; n<=k; n++) first.filter(n);
  }
}

Ma dobbiamo ancora modificarlo per riuscire a capire se durante il ciclo abbiamo trovato che k e' primo oppure no.

Ci sono almeno 4 varianti possibili, che vanno tutte bene.

Variante 1

Faccio conoscere a tutti i crivelli quale e' il numero da controllare. Quando un crivello sta setacciando un numero i (nella funzione filter) ed e arrivato a concludere che i e' primo oppure non e' primo, controlla se questo numero i e' uguale al numero da controllare. Se lo e' allora stampa, a seconda del caso, "il numero cercato e' primo" oppure "il numero cercato non e' primo". Negli altri casi non stampa nulla per non appesantire l'output.

In pratica:

• Nella classe Sieve aggiungo un attributo di classe (cioe' condiviso da tutti i crivelli) intero che conterra' il numero da controllare:

  static int numberToTest;
  

• Tale attributo di Sieve viene inizializzato nel main, non appena abbiamo letto k:

  Sieve.numberToTest = k;
  

• Nella classe Sieve, funzione filter, stampo se e solo se i coincide con numberToTest (in neretto la parte cambiata):

  void filter(int i)
  {
     if (myPrime==0)
     {  myPrime = i;
        if (i==numberToTest)
           System.out.println("Numero " + i + " e' primo");
     }
     else 
     {  if ((i % myPrime)==0)
        {if (i==numberToTest)
           System.out.println("Numero " + i + " non e' primo");}
        else
        {
          if (next==null) next = new Sieve();
          next.filter(i);
        }
     }
  }
  

Variante 2

Metto una variabile booleana condivisa da tutti i crivelli. In un generico momento del ciclo del main, quando eseguo first.filter(n), attaccata in coda al primo crivello first si trova una catena di crivelli, e il numero n viene fatto passare per questa catena di crivelli. Uno ed un solo crivello della catena trova che n e' primo oppure che n non e' primo. Se trova che n e' primo, gli facciamo mettere il booleano a true, se trova che non e' primo lo facciamo mettere a false. Quindi dopo ogni giro del ciclo sappiamo se n era primo o no, guardando il valore del booleano. A noi interessa guardarlo all'ultimo giro del ciclo, quello in cui n vale k.

In pratica:

• Metto nella classe Sieve una variabile di classe booleana:

  static int numberIsPrime;
  

• Nella classe Sieve, funzione filter, laddove stampavo ora invece assegno il booleano (in neretto le parti cambiate):

  void filter(int i)
  {
     if (myPrime==0)
     {  myPrime = i;
        numberIsPrime = true;
     }
     else 
     {  if ((i % myPrime)==0)
           numberIsPrime = false;
        else
        {
          if (next==null) next = new Sieve();
          next.filter(i);
        }
     }
  }
  

• Nel main, dopo che e' terminato il ciclo (cioe' dopo l'ultimo giro in cui n era k), controllo il booleano e stampo il risultato:

  if (Sieve.numberIsPrime) 
     System.out.println("Numero " + k + "primo");
  else
     System.out.println("Numero " + k + "non primo");
  

Variante 3

Noto che alla fine del ciclo nel main, ho una catena di crivelli dei quali il primo contiene 2, il secondo 3, e i seguenti contengono tutti gli altri numeri primi, l'ultimo crivello della catena contiene il numero primo piu' grande che sia minore o uguale a k. Se k era primo, questo ultimo crivello contiene proprio k.
Percio' per sapere se k e' primo basta andare a prendere l'ultimo crivello e guardare che numero ha dentro.

In pratica:

• L'unica modifica e' nel main, dopo il ciclo. Aggiungo del codice che scorre la lista dei crivelli a partire dal primo, andando avanti al seguente fintanto che il seguente esiste. Adesso sono sull'ultimo crivello: guardo se il numero contenuto e' proprio k.

  Sieve last = first; // parte dal primo
  while (last.next!=null) last = last.next; // avanza finche' puo'
  // ora last e' l'ultimo crivello
  if (last.myPrime==k)
     System.out.printn("Numero " + k + " primo");
  else
     System.out.printn("Numero " + k + " non primo");
  

Variante 4

Come nella variante 2, noto che alla fine del ciclo nel main, ho una catena di crivelli contenenti ciascuno un numero primo. Se k era primo, un crivello contiene proprio k.
Noto anche che la catena di crivelli non e' altro che una lista di interi. Sulle liste di interi abbiamo visto la funzione che controlla se un elemento e' presente nella lista, cercandolo nella lista. Percio' definisco nella classe Sieve la funzione che ricerca un numero in una lista (vedere dispense).

Allora in pratica:

• Aggiungo nella classe Sieve la funzione:

  boolean search(int x)
  {
    if (x==myPrime) return true;
    else 
    {
      if (next!=null) return next.search(x);
      else return false;
    }
  }
  

• Nel main, dopo aver eseguito il ciclo, chiamo su first la funzione search per cercare k nella lista. Se lo trovo, k e' primo, altrimenti k non e' primo.

  if (first.search(k))
     System.out.printn("Numero " + k + " primo");
  else
     System.out.printn("Numero " + k + " non primo");