[Java] Crivello di Eratostene con una LinkedList

[AR89]

Il Crivello di Eratostene serve a trovare i numeri primi, dato un numero n il crivello torva tutti i numeri primi da 2 a n. Per farlo trova per prima cosa il minimo (che all'inizio è 2, nn si parte dall'uno) e poi toglie tutti i suoi multipli (lui compreso, che però si conserva da un'altra parte in quanto numero primo), si trova poi di nuovo il min e ripete l'operazione finché nn si trovano tutti i numeri primi.
Ecco il codice che mi dà problemi:

package eratostene;

import java.util.*;

public class CrivelloLL extends CrivelloAstratto{
	private final int N;
	private List<Integer> crivello= new LinkedList<Integer>();
	private List<Integer> primi= new LinkedList<Integer>();
	public CrivelloLL(final int N){
		if (N<2) throw new IllegalArgumentException();
		this.N=N;
		for (int i=2; i<=N; i++)
			crivello.add(i);
	}//costruttore
	public Iterator <Integer> iterator(){
		return primi.iterator();
	}//iteratore
	public int size(){return primi.size();}
	public void filtra(){
		while (!crivello.isEmpty()){
			int min=crivello.iterator().next();//prendo il minimo
			primi.add(min);//essendo 2 lo metto nella LL dei numeri primi
			int multiplo=min;//inizializzo il multiplo
			while(multiplo<=N){
				crivello.remove(multiplo);//rimuovo i mult
				multiplo+=min;//riassegno i mult del min
			}//while
		}//while
	}//filtra
	public static void main (String args[]){
		int n=500;
		Crivello c=new CrivelloLL(n);
		c.filtra();
		System.out.println(c);
	}//main

}//CrivelloLL

Quest è l'errore che mi vine riportato:

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 334, Size: 333
	at java.util.LinkedList.entry(LinkedList.java:365)
	at java.util.LinkedList.remove(LinkedList.java:357)
	at eratostene.CrivelloLL.filtra(CrivelloLL.java:25)
	at eratostene.CrivelloLL.main(CrivelloLL.java:43)

E questa è la classe astratta da cui eredita:

package eratostene;
import java.util.*;

public abstract class CrivelloAstratto implements Crivello {
	public int size(){
		int c=0;
		for (int x: this) c++;
		return c;
	}//size
	public String toString(){
		int c=0;
		StringBuilder sb= new StringBuilder(500);
		for (int x: this){
			sb.append(String.format("%10d", x));
			c++;
			if (c%8==0) sb.append('\n');
		}//for
		return sb.toString();
	}//toString
	public int hashCode(){
		final int MOLT=43;
		int h=0;
		Iterator<Integer> it= this.iterator();
		while (it.hasNext()){
			int x= it.next();
			h=h+MOLT+x;
		}//while
		return h;
	}//hashCode
	public boolean equals (Object o){
		if (!(o instanceof Crivello)) return false;
		if (o==this) return true;
		Crivello c= (Crivello)o;
		Iterator<Integer> i1= this.iterator();
		Iterator<Integer> i2= c.iterator();
		while (i1.hasNext()){
			int x1=i1.next();
			int x2=i2.next();
			if (x1 != x2) return false;
		}//while
		return true;
	}//equals
}//CrivelloAstratto

Il problema sta nel metodo filtra(), ma nn riesco a capire perché, deve esserci qualcosa che mi sfugge sul funzionamento delle LinkedList.
Lo stesso codice, utilizzando dei TreeSet funziona, perché?

[LeleFT]

Senza guardare la tua implementazione del crivello, ti spiego cosa significa quell'eccezione: stai cercando di recuperare l'elemento in posizione 334 di un array che contiene solo 333 elementi.

Il punto in cui effettui questo sconfinamento è scritto nel trace dell'eccezione:

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 334, Size: 333
	at java.util.LinkedList.entry(LinkedList.java:365)
	at java.util.LinkedList.remove(LinkedList.java:357)
	at eratostene.CrivelloLL.filtra(CrivelloLL.java:25)
	at eratostene.CrivelloLL.main(CrivelloLL.java:43)

Ovvero, nel file CrivelloLL.java, alla riga 25.

A te capire perchè vai a sconfinare...


Ciao.

[AR89]

crivello.remove(multiplo);

questo è quello che c'è su quella riga.
Nn riesco a capire perché sconfina perché lo stesso codice funziona su un TreeSet, quindi nn vedo in che modo possa andare a sconfinare, la condizione del while mi sembra corretta e anche modificandola rendendola strettamente minore il problema rimane.

[LeleFT]

for (int i=2; i<=N; i++)
   crivello.add(i);

Tu parti, giustamente, ad inserire dal valore 2... il quale, però, è in posizione 0.

il metodo remove(int x) NON serve a rimuovere dalla lista il valore X, ma il valore in posizione X... chiaro, che se gli passi il multiplo, stai usando in modo errato il metodo.

Se, ad esempio, ho una lista che contiene solo il 2, la lista ha 1 solo elemento, in posizione 0... non posso, quindi, richiamare il metodo remove(2). Java non sa che tu vuoi eliminare l'elemento "2", ma pensa che tu voglia eliminare l'elemento in posizione 2... e non lo trova, giustamente.


Ciao.

[lucaGOfvg]

Mi sembra che l'errore possa essere nell'uso di remove.
Il metodo "remove" elimina l'elemento della lista con indice passato come parametro, ma se tu ad una lista di 500 elementi cominci ad eliminare a destra e a manca il contenuto, la lista non rimane più di 500 elementi... ed ecco l'eccezione out of bounds.
Inoltre già dopo la prima eliminazione rimuovi elementi sbagliati.
Se tu chiami crivello.remove(15), non rimuovi il numero 15 dalla lista, bensì il 15° elemento.
Consiglio di usare un Array oppure di scrivere un metodo che va a cercare l'elemento da eliminare nella lista, oppure sostituire l'elemento con 0 invece di rimuoverlo.

[lucaGOfvg]

azz! preceduto di un minuto