[java] esercizio Numero primo

[agostinomiranda]

Salve a tutti
ho difficoltà su questo esercizio
Costruire un programma che inserisce in un array i numeri primi. Chi riuscirà a portarmi l'esercizio con l'array più grande, e quindi il numero primo più grande riceverà un voto in più all'esame.


Dapprima avevo pensato a un for con un indice di tipo unsigned long, ma mi sembra troppo banale costruirlo.
Poi ho pensato alla classe BigInteger, ma non so come costruirlo mi aiutate?

[Tanino Rulez]

azz agostì,vieni a chiedere sul forum ;D

[agostinomiranda]

Non vedo cosa c'è di strano, perchè tu sei riuscito a trovare la soluzione?

e poi quando ho difficoltà anzichè rinunciare cerco delle risposte, anche perchè il forum del professore non funziona.

[nether]

non ho capito i dubbi su cosa sono... e' concettualmente uguale farlo usando "long" o "BigInteger"

[prog]

public class NumeriPrimi {
    
    //variabile di tipo long
    int numero=0;
    //array di tipo int
    int[] numeri;
    
    /** Creates a new instance of NumeriPrimi */
    public NumeriPrimi(int aN) {
        //inizializzo le proprietà della classe
        this.numero=aN;
        this.numeri=new int[this.numero];
        inizializzaNumeri();
    }
    
    /**Calcola i primi n numeri primi minore uguale di n
     *con il criterio Eratostene
     */
    public void calcolaPrimi(){
        for(int i=2;i<this.numeri.length;i++){
            //controllo che il valore della posione i dell'array sia diversa da -1
            if(this.numeri[i]!=-1) {
                //inizio a controllare che l'elemento i+1 dell'arrray
                //non sia un multiplo dell'elemento i della'array
                for(int j=i+1;j<this.numeri.length;j++) {
                    //controllo che il valore della posione j dell'array sia diversa da -1
                    if(this.numeri[j]!=-1) {
                        //controllo che l'elemento della j posizione dell'array
                        //non sia un multiplo dell'elemento della posizione i dell'array
                        if((this.numeri[j]%this.numeri[i])==0) {
                            //elimino l'elemento di posizione j dell'array
                            //in quanto multiplo dell'elemento dell'array di posione i
                            this.numeri[j]=-1;//eliminazione fittizia
                        }
                    }
                }
            }
        }
        stampaPrimi();
    }
    
    /**questo metodo stampa i numeri primi
     *
     */
    private void stampaPrimi(){
        System.out.println("Numeri primi compresi tra 0 e "+numero);
        for(int i=2;i<this.numeri.length;i++) {
            if(this.numeri[i]!=-1){
                System.out.println(this.numeri[i]);
            }
        }
    }
    
    public static void main(String[] arg){
        NumeriPrimi primi=new NumeriPrimi(120);
        primi.calcolaPrimi();
    }
    
    /**Questo metodo inizializza l'array che conterrà i numeri
     *da cui calcolare quelli primi
     */
    private void inizializzaNumeri() {
        for(int i=2;i<this.numeri.length;i++){
            this.numeri[i]=i;
        }
    }
    
} 

questo metodo utilizza il Crivello di Eratostene maggiore informazione sui numeri primi puoi trovarle wikipedia.it.
Cmq la classe lo scritta in fretta a funzionare funziona ma bisogna ottimizzarla per quanto riguarda la struttura dati infatti come ho fatto se devi calcolare i numeri primi tra 0 e 10000 devi avere un vettore con 10000 elementi, potresti ottimizzare memorizzando solo i numeri primi e non tutti i numero

[prog]

Ho modificato la classe ora memorizzi solo i numeri primi.

import java.util.ArrayList;
import java.util.Iterator;

public class NumeriPrimi {

//variabile di tipo long
int numero=0;
//array di tipo int
int[] numeri;
//variabile oggetto di tipo ArrayList
ArrayList<Integer> primi=new ArrayList<Integer>();

/** Creates a new instance of NumeriPrimi */
public NumeriPrimi(int aN) {
//inizializzo le proprietà della classe
this.numero=aN;
this.numeri=new int[this.numero];
//inizializzaNumeri();
}

/**Calcola i primi n numeri primi minore uguale di n
*con il criterio Eratostene
*/
public void calcolaPrimi(){
boolean sentinella;
Iterator<Integer> iteratore=null;
if(this.numero>=2){
//inizio ad inserire il primi numero primo 2
primi.add(2);
}
for(int i=3;i<=this.numero;i++){
//ottengo l'iteratore per scandire gli alementi della ArrayList primi
iteratore=primi.iterator();
//inizio il confronto degli elementi
sentinella=true;
while(sentinella && iteratore.hasNext()) {
//controllo se il numero i è multiplo di quanlke numero primo gia nella ArrayList
if((i%iteratore.next())==0) {
sentinella=false;
}
}
//controllo se l'elemento deve essere in quanto nmero primo
if(sentinella) {
primi.add(i);
}
}
stampaPrimi();
}

/**questo metodo stampa i numeri primi
*
*/
private void stampaPrimi(){
if(this.numero<=1){
System.out.println("Nè 0 nè 1 sono numeri primi");
} else {
System.out.println("Numeri primi compresi tra 0 e "+numero);
//istanzio un Iterator per la ArrayList
Iterator<Integer> iteratore=primi.iterator();
//scorro tutta la ArrayList
while(iteratore.hasNext()){
System.out.println(iteratore.next());
}
}
}



public static void main(String[] arg){
NumeriPrimi primi=new NumeriPrimi(120000);
primi.calcolaPrimi();
}
}