Laufzeit Primzahlgenerator

Diskutiere Laufzeit Primzahlgenerator im Allgemeine Java-Themen Forum; Servus, hat jemand von euch schon mal einen Primzahlgenerator geschrieben? Wie sehen die Laufzeiten aus? Meine Ausgaben (Code nicht...

  1. ssoul26
    ssoul26 Mitglied
    Servus,

    hat jemand von euch schon mal einen Primzahlgenerator geschrieben? Wie sehen die Laufzeiten aus?

    Meine Ausgaben (Code nicht optimiert, Core 2 Duo 2GHz):

    1. DEBUG
    Generierte Primzahlen: 12000
    Laufzeit: 2.0 s

    2. DEBUG
    Generierte Primzahlen: 25000
    Laufzeit: 10.0 s

    3. DEBUG
    Generierte Primzahlen: 50000
    Laufzeit: 32.0 s


    Würd mich über Beiträge freuen :toll:
     
  2. Vielleicht hilft dir dieses Training hier weiter.
  3. redJava99
    redJava99 Mitglied
    Hi,
    hab gerade was zusammengetippt und die Statistik sagt:

    generated 11301 primes < 120000 in 0.8 seconds.
    generated 25997 primes < 300000 in 6.3 seconds.
    generated 49098 primes < 600000 in 10.1 seconds.

    Auf einem Kern mit 4,2 GHz. Quadcore geringfügig schneller, viel zu parallelisieren gibts da nicht.
     
  4. JCODA
    JCODA Aktives Mitglied
    Duration for generating 78.498 primes < 1.000.000 : 23 ms
    Duration for generating 664.579 primes < 10.000.000 : 178 ms
    Duration for generating 5.761.455 primes < 100.000.000 : 3.079 ms
    Duration for generating 50.847.534 primes < 1.000.000.000 : 35.678 ms
    Duration for generating 98.222.287 primes < 2.000.000.000 : 78.997 ms

    auf einem Kern mit 3.5 GHz von einem Quadcore.
     
    Zuletzt bearbeitet: 18. März 2014
  5. ssoul26
    ssoul26 Mitglied
    Ihr seit ja ziemlich schnell :) Überprüft ihr die Richtigkeit der generierten Primzahlen (gegenüberstellen mit schon vorhandenen Listen)? Welches Prinzip implementiert ihr?
     
    Zuletzt bearbeitet: 18. März 2014
  6. redJava99
    redJava99 Mitglied
    Ich machs nach der Hau-Drauf-Methode:
    Gefundene Primzahlen = {2}
    Für jede Zahl k = {3,..n} prüfe ich auf Teilbarkeit durch alle bereits gefundenen Primzahlen.
    Ist keine kleinere Primzahl Teiler, ist k eine Primzahl und kommt in die Liste.
    Der Test auf Korrektheit erfolgt damit implizit.

    Bei JCODA interessiert mich die Methode auch brennend - die Dauer ist ja schon um einiges kürzer. Dafür findet er im angegebenen Intervall mehr Primzahlen als es eigentlich gibt. Beruhigt mich doch sehr ;-)

    [Edit: JCODA hat seine Statistik korrigiert. Bleibt nur noch die Frage nach der Implementierung...]
     
    Zuletzt bearbeitet: 18. März 2014
  7. JCODA
    JCODA Aktives Mitglied
    Ich hab vor 9 Minuten eine "bugfreie" Version reineditiert.
    Ich benutze das Sieb des Eratosthenes ? Wikipedia

    Und wenn ich die Optimierung vom Wiki einbaue, erhalte ich sogar:

    Duration for generating 78.498 primes < 1.000.000 : 24 ms
    Duration for generating 664.579 primes < 10.000.000 : 142 ms
    Duration for generating 5.761.455 primes < 100.000.000 : 2.004 ms
    Duration for generating 50.847.534 primes < 1.000.000.000 : 23.982 ms
    Duration for generating 98.222.287 primes < 2.000.000.000 : 48.667 ms
     
    Zuletzt bearbeitet: 18. März 2014
  8. ssoul26
    ssoul26 Mitglied
    Das Sieben ist wahrhaftig schwer zu toppen:)

    Hab ein bisschen feintuning getrieben. So mal aktualisierte Zeiten (Core 2 Duo 2GHz):


    1. DEBUG
    Generierte Primzahlen: 100000
    Laufzeit: 2.0 s

    2. DEBUG
    Generierte Primzahlen: 250000
    Laufzeit: 7.0 s

    3. DEBUG
    Generierte Primzahlen: 700000
    Laufzeit: 32.0 s
     
  9. ssoul26
    ssoul26 Mitglied
    Neuer Testlauf mit einem i7.

    Wie machst du das so schnell?? Über 90 Millionen Zahlen so schnell? Oder hab ich da einen Denkfehler:)


    DEBUG
    Generierte Primzahlen: 10000000
    188540587
    Laufzeit: 160.0 s
     
  10. Highchiller
    Highchiller Neues Mitglied
    Wie wärs mit dem Sieb von Atkin?

    Laut Wiki ist Erathos in O(N) operationen wobei Atkin in O(N/(log(log(N))) operationen läuft ;)
     
  11. klauskarambulut
    klauskarambulut Mitglied
    i3-3220 @3.3 GHz

    Code (Text):
    Duration for generating 4 primes < 10 : 0 ms
    Duration for generating 25 primes < 100 : 0 ms
    Duration for generating 168 primes < 1.000 : 1 ms
    Duration for generating 1.229 primes < 10.000 : 10 ms
    Duration for generating 9.592 primes < 100.000 : 8 ms
    Duration for generating 78.498 primes < 1.000.000 : 11 ms
    Duration for generating 664.579 primes < 10.000.000 : 67 ms
    Duration for generating 5.761.455 primes < 100.000.000 : 1.313 ms
    Duration for generating 50.847.534 primes < 1.000.000.000 : 15.977 ms
    Duration for generating 98.222.287 primes < 2.000.000.000 : 32.846 ms
    Duration for generating 105.097.564 primes < 2.147.483.647 : 35.927 ms
    Wieviel speicher gibt denn JCoda seiner VM mit? :)
     
  12. Wenn du Java lernen möchtest, empfehlen wir dir dieses Online-Training hier
Passende Stellenanzeigen aus deiner Region:





Die Seite wird geladen...

Laufzeit Primzahlgenerator - Ähnliche Themen

Laufzeitanalyse
Laufzeitanalyse im Forum Hausaufgaben
Exponentielle Laufzeit zeigen
Exponentielle Laufzeit zeigen im Forum Hausaufgaben
Automatisches Methoden Laufzeiten logging?
Automatisches Methoden Laufzeiten logging? im Forum Allgemeine Java-Themen
Objekt Typ zur Laufzeit ermitteln
Objekt Typ zur Laufzeit ermitteln im Forum Java Basics - Anfänger-Themen
Datei im Package zur Laufzeit editieren
Datei im Package zur Laufzeit editieren im Forum Java Basics - Anfänger-Themen
Thema: Laufzeit Primzahlgenerator