größerer Datentyp als long

[èner]

Hallo,
ich möchte ein Programm zum errechnen von Primzahlen schreiben. Da sich ein paar Freunde bereit erklärt haben dieses auch auf ihren Rechner laufen zu lassen, schreibe ich das ganze so, dass mein Rechner nur noch als Server fungiert, und die "Drecksarbeit" machen fremde Rechner. Allerding reicht bei diesem Projekt nach wenigen Tagen rechenarbeit der Datentyp long nicht mehr. Gibt es alternativen, um mit größeren integer-Werten zu arbeiten??

M.f.G. Èner

[Daniel Thoma]

Hallo èner,

Allerding reicht bei diesem Projekt nach wenigen Tagen rechenarbeit der Datentyp long nicht mehr.

Bis 2^64 brauchst Du schon mehrere Tage? Ich hab mich mit dem Thema nie näher beschäftigt, wie testest Du denn Primalität einer Zahl?

Gibt es alternativen, um mit größeren integer-Werten zu arbeiten?

Ja, schau Dir die Klasse http://java.sun.com/javase/6/docs/api/java/math/BigInteger.html@BigInteger an. Damit kannst Du Zahlen darstellen, bis Dir der Speicher ausgeht. Allerdings sind Operationen auf großen Zahlen natürlich nicht mehr in konstanter Zeit möglich.

Grüße

Daniel

[Daniel Thoma]

Ja, schau Dir die Klasse BigInteger an.

So sollte das aussehen...

[Éner]

Hallo èner,

Allerding reicht bei diesem Projekt nach wenigen Tagen rechenarbeit der Datentyp long nicht mehr.
Bis 2^64 brauchst Du schon mehrere Tage? Ich hab mich mit dem Thema nie näher beschäftigt, wie testest Du denn Primalität einer Zahl?

Also ich hab jetzt einfach mal das hier geschrieben:
 ~~~java

public static void prim() {
  long start = 0;
  long end = 1;
  long i = 0;
  long cur;
  boolean lost = false;
  try {
   String input;
   BufferedReader inoutstream;
   inoutstream = new BufferedReader(new InputStreamReader(System.in));
   input = inoutstream.readLine();
   start = Long.parseLong(input);
   input = inoutstream.readLine();
   end = Long.parseLong(input);

}
  catch(IOException a) {
   a.printStackTrace();
  }

for (cur = start; cur <= end; ++cur) {
   lost = false;
   for (i = 2; (i*2) <= cur && lost != true; ++i) {
    if ((cur % i) == 0) {
     lost = true;
    }
   }
   if (lost != true) {
    System.out.println(cur + " ist eine Primzahl");
   }
  }
 }

  
Natürlich muss ich das noch mit einem Client-Socket-Prinzip "kreuzen"...  

[Daniel Thoma]

Hallo Éner,

Ok, Du probierst einfach alle Zahlen die kleiner als die Wurzel sind als mögliche Teiler durch. Das ist ungefähr die langsamste Methode.

Guck Dir mal http://de.wikipedia.org/wiki/Primzahltest an.
Ich würde versuchen einen randomisierten, schnellen Test zu verwenden (Miller-Rabin z.B.) und damit erstmal die Zahl der Kandidaten deutlich zu reduzieren. Da diese Tests Fehler machen, muss man dann noch einen langsameren Test nachschalten. Irgend ein verbesserter Fermat-Test bietet sich da an.

Grüße

Daniel

[èner]

Vielen Dank für diese ganzen Tipps!

...muss man dann noch einen langsameren Test nachschalten. Irgend ein verbesserter Fermat-Test bietet sich da an.

Was bringt es das ganze zweimal zu machen - reicht es nicht wenn man nur die langsamere Technik nimmt?

M.f.G. Éner

[Daniel Thoma]

Hallo èner,

Was bringt es das ganze zweimal zu machen - reicht es nicht wenn man nur die langsamere Technik nimmt?

Doch aber es ist langsamer ;-)
Der Miller-Rabin-Test ist immer korrekt, wenn er feststellt, dass eine Zahl keine Primzahl ist. Mit einer sehr geringen Wahrscheinlichkeit erkennt er allerdings eine Zahl als Primzahl, wenn sie keine ist.
Damit musst Du den aufwendigen Test praktisch nur durchführen, wenn Du tatsächlich eine Primzahl gefunden hast.
Für praktische Anwendungen (Verschlüsselung u.ä.) verzichtet man wohl sogar darauf, das nochmal zu überprüfen. Aber wenn Du eben wirklich beweisen willst, dass Du eine Primzahl hast, musst Du das nochmal prüfen.

Grüße

Daniel