Ich war kürzlich Teil eines kleinen Java-Programmierwettbewerbs an meiner Schule. Mein Partner und ich haben gerade unsere erste reine oop-Klasse beendet und die meisten Fragen waren außerhalb unserer Liga, also haben wir uns auf diesen hier festgelegt (und ich paraphrasiere etwas): "gegeben eine Eingabe-Ganzzahl n zurück die nächste int, die Prime ist und seine Umkehrung ist auch zum Beispiel prime, wenn n = 18 Ihr Programm 31 "drucken sollte, weil 31 und 13 beide prime sind. Ihre .class-Datei würde dann einen Testfall von allen möglichen Zahlen von 1-2.000.000.000 haben, die an sie übergeben wurden, und sie musste die richtige Antwort innerhalb von 10 Sekunden zurückgeben, um als gültig betrachtet zu werden.
Wir haben eine Lösung gefunden, aber bei größeren Testfällen würde es länger als 10 Sekunden dauern. Ich bin mir ziemlich sicher, dass es eine Möglichkeit gibt, den Bereich der Schleifen von n, .. 2.000.000.000 zu verschieben, da die Wahrscheinlichkeit, dass wir so weit schleifen müssen, wenn n eine niedrige Zahl ist, klein ist, aber so oder so ist Prime unter beiden Bedingungen gefunden. Zuerst schleifen wir von 2, .., egal wie groß es war, dann erinnerte ich mich an die Regel, nur die Quadratwurzel von n zu durchlaufen. Irgendwelche Vorschläge, wie ich mein Programm effizienter machen kann? Ich habe keine Kurse gehabt, die sich mit der Komplexitätsanalyse von Algorithmen befassen. Hier ist unser Versuch.
%Vor%tut mir leid, wenn ich die Formatierung für den Code falsch gemacht habe, ist dies mein erstes Mal hier posten. Auch die Ausgabe musste nach jeder Zeile ein '#' haben, das ist die Zeile nach der Schleife. Danke für jede Hilfe, die ihr anbietet !!!
Zuerst sollten Sie alle Primzahlen bis zu 2.000.000.000 vorberechnen, indem Sie etwas wie das Sieb von Eratosthenes verwenden. Sie können speichern, ob jede Zahl in einem Bit-Array prim ist.
Das ist ziemlich schnell, und dann ist das Überprüfen jeder einzelnen Zahl auf Primalität eine einfache Suche.
Wenn Sie dies nicht tun können, weil Sie für jeden Testfall eine neue Instanz Ihres Programms ausführen müssen, verwenden Sie einen schnellen Primalitäts-Testalgorithmus wie Miller-Rabin .
Ihre Hauptprüfung ist sehr ineffizient. In der Tat müssen Sie die Vielfachen der bereits geprüften Zahlen nicht noch einmal überprüfen. Wenn Sie also nach% 2 suchen, müssen Sie nicht nach% 4 suchen.
Um herauszufinden, ob eine Zahl eine Primzahl ist, müssen Sie nur versuchen, sie durch alle bekannten Primzahlen zu teilen, bis Sie die Quadratwurzel der zu prüfenden Zahl erreicht haben. Dadurch verringert sich die Anzahl der Divisionen erheblich: Wenn Ihre App eine Liste der Primzahlen von 2 .. ~ 44721 hat (zum Beispiel als Vorbereitungsschritt berechnet), können Sie alle Zahlen bis 2000000000 ziemlich schnell überprüfen.
Sie sollten auch sicherstellen, dass Sie zuerst die kleinere der beiden Permutationen überprüfen (z. B. in Ihrer Probe zuerst 13, dann 31).
Bearbeiten:
Hier ist ein Beispiel, das ich schnell in C # zusammensetze (Sie müssen einige geringfügige syntaktische Änderungen vornehmen, damit es auf Java läuft, aber ich hatte gerade einen C # -Compiler zur Hand):
%Vor% Auf meinem Computer und mit der gegebenen loop und n in der Quelle erscheint das Ergebnis sofort.
Verwenden Sie BigInteger.isProbablePrime(certainty) und < a href="http://java.sun.com/javase/6/docs/api/java/math/BigInteger.html#nextProbablePrime ()"> BigInteger.nextProbablePrime() kann die Anzahl der Fälle erheblich reduzieren Sie müssen sehr effizient prüfen
Es sieht so aus, als würden Sie um 1 erhöhen, aber Sie sollten um 2 inkrementieren. Keine gerade Zahl ist Primzahl, sondern 2.
Die große Ineffizienz hier ist Ihre Haupttestmethode prime . Denken Sie darüber nach, wie oft genau dieselben Zahlen getestet werden müssen, und konzentrieren Sie sich darauf, wie Sie die Speicherstrukturen nutzen können, um einige der wiederholten Berechnungen zu vermeiden.
Ich habe das vorher nicht gemacht, aber hier sind einige Dinge, die mir in den Sinn kommen.
Wenn Ihr Quadratwurzel eine Ganzzahl ist, ist die Zahl nicht prim
wenn die Zahl in einem 0,2,4,5,6 endet, oder 8 ist es nicht prim / außer 2 selbst
Die Zahl kann durch 3 geteilt werden, wenn die Summe der Ziffern durch 3 teilbar ist und um 9 wenn die Summe 9 ist.
Ich weiß nicht, ob das Testen für diese Dinge Ihnen hilft, zumindest sollte der Test des squareRoot helfen, weil Sie es sowieso berechnen müssen und Sie können schon fertig sein.
Oh, und natürlich wird Ihre Wirkung viel zunehmen, wenn Sie so etwas wie Miller-Rabin-Primalitätstest Ссылка machen. Ihr tatsächlicher Test muss nur in den Fällen durchgeführt werden, die nicht sicher sind.
Eine weitere Geschwindigkeitsverbesserung, die Sie in main vornehmen können, besteht darin, Ihre Schleife zu ändern, um einige zusammengesetzte Zahlen vorzufiltern und einige Iterationen in eine Testreihenfolge abzurollen. Am einfachsten ist es, 2 außerhalb der Schleife zu testen und dann ungerade Zahlen ( 2*i+1 ) zu testen. Etwas komplexer ist es, 2, 3 und dann 6*i ± 1 zu testen. Sie können diesen Ansatz erweitern, indem Sie die ersten n Primzahlen testen und dann den Ofen pn# * i+j durchlaufen, wobei p n die Primzahl ist primordial (das Produkt der ersten n Primzahlen) und j ist eine positive ganze Zahl kleiner als und gleichzeitig mit p
Um die Methode prime zu beschleunigen, könnten Sie mit einem schnellen probabilistischen Primetest beginnen und testen ein langsamerer deterministischer Test nur für jene Fälle, die der probabilistische Test nicht bestimmen kann.
@outis ... ich sehe, was du sagst, das ist ein hübscher kleiner Trick, den ich sagen muss. Danke dafür.
@Graham ... auch cool, ich habe einen Artikel über den Test gelesen, den du erwähnt hast, obwohl ich glaube, ich habe den Kern davon aus den Kommentaren verstanden, die du gemacht hast. Python sieht für mich immer wie griechisch aus. Ich weiß, dass jeder sagt, dass es eine der einfacheren Sprachen ist, aber java und c ++ sehen für mich immer lesbarer aus. Jedenfalls wäre das ein viel besserer Weg gewesen. Nochmals vielen Dank an alle, die mir Tipps gegeben haben, die ich von diesem Board gelernt habe. Kann nicht für meine Datenstrukturen und Algorithmen Klasse im Herbst !!!
Die einfachste Option wäre die Verwendung einer vorhandenen großen Ganzzahlbibliothek. Es wird keine Fehler haben, und es wird alle unterstützenden Funktionen zur Verfügung stellen.
Wenn Sie Ihre eigene Implementierung (z. B. für eine Zuweisung) schreiben, würde ich empfehlen, mit einem Pseudocode-Algorithmus in einem Buch zu arbeiten, damit Sie verstehen, was Sie tun.
Eine der einfachsten Methoden ist es, Jacobi und Legendre zu verwenden und nach Gleichheit zu vergleichen. Ich habe gerade eine Aufgabe für die RSA-Verschlüsselung eingereicht. Hier ist, was ich für die einfache Genauigkeit getan habe, aber die Algorithmen sind allgemein und arbeiten auch für Vielfache-Präzision-Ganzzahlen.
%Vor%Die Leistung ist auch bei großen Zahlen sehr gut.
@David erhalten Sie die Quadratwurzel einer Zahl und dann Schleife, bis die Quadratwurzel gerade Zahlen zu beseitigen und sehen, ob es nicht teilbar ist
Noch schneller als all das verwendet den Miller-Rabin -Test. Es ist ein probabilistischer Test und hat daher ein gewisses Maß an Fehlern; Der Test wird jedoch mehrmals ausgeführt, wodurch der Fehler so klein wie nötig verkleinert wird (50 reicht oft für kommerzielle Anwendungen aus).
Nicht in Java, aber hier ist eine schnelle Implementierung in Python, die ich mir ausgedacht habe.