# Primzahl || Primfaktorzerlegung -> Eure Laufzeiten *Wen es halt interessiert*



## ssoul26 (13. Jul 2012)

Hallo Leute,
wäre cool, wenn es euch natürlich nur Spass macht und interessiert, eure Laufzeiten für die Primzahlfaktorenzerlegung folgender Zahl angibt:
6750622348964143051956305469326962117763788889781985387

Bei mir liegt die Berechnungszeit bei mehreren Minuten, soll wohl in unter 2 Sekunden machbar sein, wobei der Algorithmus natürlich noch sehr Trivial gehalten ist. Bei der Erkennung ob es sich um eine Primzahl handelt oder nicht, liege ich hier natürlich im 0 ms Bereich.

Wie könnte man es verbessern -> ohne Multithreading! 


```
/**
    * Test Zerlegung in Primzahlfaktoren (BigInteger).
    * 
    * @param Zu zerlegende Zahl
    * @return Liste der BigInteger-Objekte
    */
   public static ArrayList<BigInteger> getFaktoren(BigInteger zahl) {
      ArrayList<BigInteger> faktoren = new ArrayList<BigInteger>();
      BigInteger teiler = new BigInteger("2");
      while (!isPrime(zahl)) {
         if (zahl.mod(teiler).compareTo(BigInteger.ZERO) == 0) {
            faktoren.add(teiler);
            zahl = zahl.divide(teiler);
         } else {
            teiler = teiler.add(BigInteger.ONE);
         }
      }
      faktoren.add(zahl);
      return faktoren;
   }
```


----------



## Gast2 (13. Jul 2012)

http://www.java-forum.org/codeschnipsel-u-projekte/101333-primfaktorzerlegung.html

Damit dauerts knapp ne halbe Sekunde. Vielleicht hilft dir der Code ja.


----------



## ssoul26 (13. Jul 2012)

EikeB hat gesagt.:


> http://www.java-forum.org/codeschnipsel-u-projekte/101333-primfaktorzerlegung.html
> 
> Damit dauerts knapp ne halbe Sekunde. Vielleicht hilft dir der Code ja.




Danke, für den Hinweis !


----------



## ssoul26 (13. Jul 2012)

Anbei mal paar Zeiten für die Bestätigung einer Primzahl. Habt ihr auch welche? Läuft ihr Arrays durch oder benutzt ihr eure eigene Vermutungen über Primzahlen?


Primzahltest
1000000000000000003 ist Primzahl!
Dauer : 0 s -> 0 ms


Primzahltest
737373737373737 ist Primzahl!
Dauer : 0 s -> 0 ms


Primzahltest
10000000000037 ist Primzahl!
Dauer : 0 s -> 0 ms


Primzahltest
240956189198547275841965933 ist Primzahl!
Dauer : 0 s -> 0 ms


Primzahltest
328776400614223 ist Primzahl!
Dauer : 0 s -> 0 ms


----------



## MicroBenchmark (13. Jul 2012)

Ich weis zwar nicht wie du auf deine Zeiten kommst, aber solche "Mikro-Benchmarks" sind nicht aussagekräftig. Schon gar nicht bei solche kleinen Zahlen die man sogar noch mit Taschenrechner, Papier und Bleistift in angemessener Zeit faktorisieren kann. Wenn du allerdings versuchst RSA zu knacken (n=p*q) wäre die Zeit schon mehr "Wert" da es entsprechend lange dauern würde das man die Ungenauigkeit von System.currentTimeMillis() vernachlässigen kann. Und selbst wenn sollte man zum Benchmarking eher System.nanoTime() nutzen. Kommt allerdings drauf an wie genau der Echtzeit-Taktgeber des PCs ist und wie genau das BIOS und OS diesen lesen und der VM die Werte übergeben können.

Noch eine Anmerkung zu BigInteger.isProbablePrime(int) : diese Methode ist absoluter Schrott ! Selbst bei "kleinen" Zahlen im Bereich 10mio - 100mio gibt diese Methode für Zahlen die auf "5" enden TRUE, was ja nun mal eindeutig falsch ist da man jede Zahl die auf "5" endet durch 5 teilen kann. Auch werden in bestimmten bereichen 10er Potenzen *also alles auf "0"* als PRIME anerkannt. Und je größer man den Zahlenbereich wählt *ich habs mal bis zum StackOverflow mit ner Zahl mit 40 Stellen versucht* treten immer mehr Fehler auf : Zahlen welche durch 2 , 3 , 5 , 9 , 10 usw teilbar sind werden als PRIME erkannt. (Ich habe bewusst 2,3,5,9 und 10 gesagt da man diese am einfachsten erkennt : 2 : gerade , 5 : 5/0 am Ende , 10 : 0 am Ende , 3 : Quersumme durch 3 , 9 : Quersumme durch 9.)

Obwohl BigInteger (fast) alles an StrictMath delegiert treten solche "einfachen" Fehler auf die man egal wie groß die Zahl ist sogar mit bloßem Auge erkennt ohne rechnen zu müssen (außer Quersumme). Warum wurde sowas nicht in StrictMath eingebaut ? Klar ist es für einen Rechner schwer solch große Zahlen zu verwenden weil die Darstellung in Bits eine ganz andere ist, aber zumindest sollte es vermieden werden das durch 2 teilbare Zahlen als PRIME erkannt werden ... weil es ist sehr einfach für einen Rechner [c]x&0x01==0x01[/c] zu ermitteln. Aber für Java ja scheint das ja selbst mit Bit-rumgewürfel problematisch zu sein.

Also entweder nimmt man hohe Laufzeiten für korrekte Ergebnisse hin oder muss mit "false positives" rechnen.


----------



## ssoul26 (13. Jul 2012)

Danke Micro für deine Ausführungen! Na, ich versuch hier nichts zu knacken, hab ich nicht nötig!! Hättest du eine Primzahl die etwas länger ist? Bis zu 1000-Stellen max Will nur die Performance teste und Richtigkeit, finde aber leider keine Großen zahlen. Habe zwar auch einen Generator, aber ob da alles richtig ist, das weiss ich nicht

Meine Zeiten messe ich ganz simpel-> Methoden - Ein-/Ausgang.


----------



## Gast2 (13. Jul 2012)

Primzahl ? Wikipedia

Da stehen nen paar große bis sehr große Primzahlen.


----------



## ssoul26 (13. Jul 2012)

Oh man, ich steh heut aufm Schlauch Thx, Eike!


----------



## Ikaron (13. Jul 2012)

Könntest du mal bitte den kompletten Sourcecode von einem funktionierenden Programm mit der riesen Zahl posten? Ich würd das gerne testen, aber mein (leicht vervollständigter) Code läuft schon seit 30+min, und ist noch nicht fertig, und das auf einem 3,6GHz Prozessor mit eig. nichts im Hintergrund am laufen..


----------



## Gast2 (13. Jul 2012)

Sourcecode steht im ersten verlinkten Thread. Ne große Primzahl auf der zweiten Verlinkten Seite.
Was führst du aus? Mit welcher Eingabe?


----------



## Ikaron (13. Jul 2012)

Ich hab's mit 6750622348964143051956305469326962117763788889781985387 versucht, was ja dann nicht geklappt hat.. Ich werd's mal mit dem Source auf der einen Seite versuchen...
[edit]Jetzt hat's bei der Zahl ca 263279219ns gedauert... Das entspricht 2,6s, oder?[/edit]
[edit]Scheint aber ungenau zu sein.. Bei 2^521-1 spuckt er lauter Zahlen aus - Das ist aber laut Wikipedia eine Primzahl?[/edit]


----------

