Laboratorio 02:

CRIVELLO DI ERATOSTENE E VARIANTI

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

Provare le seguenti varianti viste a lezione:

1. Versione dove ogni crivello che stampa il numero primo da lui trovato
2. Versione dove ogni crivello che stampa il numero primo da lui trovato, numerandolo (tramite il contatore counter, variabile di classe)
3. Versione dove i numeri primi vengono stampati nel main, alla fine, scorrendo la catena dei crivelli che si e' venuta a creare

Scrivere una variante che genera tutti i numeri primi minori di k, con k dato come parametro su command-line.

IN PRATICA:
Bisogna aggiungere la lettura del parametro da command-line.

Scrivere una variante che genera i primi k numeri primi, con k dato come parametro su command-line.

IN PRATICA:
La classe Sieve deve avere la variabile statica counter che conta quanti crivelli sono stati creati; il costruttote della classe Sieve deve incrementare counter.
Il ciclo for nel main della classe PNG termina quando Sieve.counter raggiunge il valore k.

Scrivere un programma che controlla se un numero e' primo oppure no (il numero e' letto da command-line).

IN PRATICA:
Sia n il numero da controllare.
E' sufficiente provare a generare tutti i numeri primi minori di n+1. Se a un certo punto si scopre che n e' primo, allora si termina e si risponde "si". Altrimenti si risponde "no".

Per chi avesse finito tutto

Scrivere un programma che calcola i fattori primi di un numero k letto da command-line.

NOTA:
I fattori primi di k vanno cercati fra i numeri primi compresi fra 2 e la parte intera superiore di k/2, ovvero (k+1)/2.
Una volta trovato un fattore primo, si divide k per tale fattore e si ripete, fino a che dividendo non otteniamo 1.

IN PRATICA:

Si scrive nella classe Sieve una nuova funzione che cerca il prossimo fattore primo di un numero i:

int primeFactor(int i)
{
...se (i % myPrime)==0 cioe' i divisibile per myPrime,
   ritorna myPrime come fattore primo di i
...altrimenti se next==null cioe' non ho altri numeri primi,
   ritorna i come numero primo (non ha divisori)
...altrimenti ritorna next.primeFactor(i)
   cioe' cerca piu' avanti nella lista di numeri primi
}

• trova un fattore primo di k, chiamando first.primeFactor(k)
• stampa tale fattore
• divide k per tale fattore