[Java] ArrayList.indexOf(Double)?

[psychofreak]

Hallo mal wieder,

diesmal versuche ich ein Programm zu schreiben, welches mir sämtliche Primfaktoren einer Zahl liefert. Zunächst sollen dafür Primzahlen nach dem Prinzip des Sieb des Eratosthenes ermittelt werden. Dazu benutze ich eine ArrayList, da man dort im Gegensatz zu Arrays Einträge streichen kann.

import java.util.ArrayList;

public class BigPrimeFactors {
 ArrayList<Double> primfaktoren = new ArrayList<Double>();
 
 ArrayList<Double> primzahlen(double bis) {
  ArrayList<Double> zahlen=new ArrayList<Double>();
  
  //Sieb füllen
  for(double i=2; i<=bis; i++) {
   zahlen.add(i);
  }

  //Zahlen streichen
  for(double i=0; i<zahlen.size(); i++) {
   for(int j=2; zahlen.get((int)i)*j<=bis; j++) {
    zahlen.remove(indexOf(new Double(zahlen.get((int)i)*j)));
   }
  }

  return zahlen;
 }

 public static void main(String[] args) {

 }
}

Das Problem befindet sich in der längsten Zeile des Programms. Der Kompiler spuckt folgendes aus:

/tmp/jc_1866/BigPrimeFactors.java:17: cannot find symbol
symbol  : method indexOf(java.lang.Double)
location: class BigPrimeFactors
    zahlen.remove(indexOf(new Double(zahlen.get((int)i)*j)));
                  ^
1 error

Ich dachte bis jetzt, dass Double genau für solche Sachen gedacht wäre. Kann mir jemand sagen, wie es richtig wäre?

[fred5261]

Dein Code hat mehrere Probleme:

- double sind Gleitkommanzahlen, Primzahlen sind aber Ganzzahlen
- wenn du indexOf benutzt, dann als Methode der List zahlen
- du machst dir die Sache viel zu umständlich, du brauchst doch bloß den Pseudocode von der Wikipedia-Seite 1:1 in Java umzusetzen

Konstrukte wie

zahlen.remove(indexOf(new Double(zahlen.get((int)i)*j)));

sind syntaktischer Unsinn und auch für diesen Algorithmus absolut unnötig.

Ein kurze Überarbeitung deines Codes könnte so aussehen:

    List<Integer> primzahlen(int grenze) {
        List<Integer> zahlen = new ArrayList<Integer>();

        for (int i = 2; i <= grenze; i++)
            zahlen.add(i);

        for (int i = 2; i * i <= grenze; i++)
            if (zahlen.contains(i))
                for (int j = i * i; j <= grenze; j += i)
                    zahlen.remove((Integer) j);

        return zahlen;
    }

Wie du siehst, ist das erheblich übersichtlicher als dein Ansatz.

[psychofreak]

Das in der Zeile mehrere Fehler drin stecken, habe ich auch schon bemerkt. Theoretisch ließe sie sich auf

zahlen.remove(zahlen.indexOf(zahlen.get((int)i)*j);

verkürzen. Dein Vorschlag ist tatsächlich besser.
Double habe ich übrigens genommen, da größrere Zahlen benutzt werden sollten. Mir ist allerdings sehr schnell aufgefallen, dass ich dafür einfach viel zu wenig Speicher habe.
Trotzdem danke.

[fred5261]

Praktisch lässt es sich noch viel weiter verkürzen:

zahlen.remove((Integer) (zahlen.get(i)*j));

Das liegt ganz einfach daran, dass remove überladen ist und nicht nur die Angabe eines Indexes sondern auch direkt des zu löschenden Objektes erlaubt.

Nur das mit dem Speicher klingt sonderbar. Dass dich eine Liste aus Zahlen in Speichernöte bringt halte ich für ziemlich abwegig.

[daboom]

Das mit dem Speicher kommt darauf an, wieviel man der VM gibt.

mit -Xmx kann man dies dann erhöhen. Wenn man über eine bestimmte Grenze hinausschießt, kann das u.U. schon nötig sein.