Problem: Ich versuche diesen Algorithmus umzuformen, um ihn schneller zu machen. Was wäre das erste Refactoring hier für Geschwindigkeit?
%Vor%Die erste Optimierung, die Sie vornehmen können, besteht darin, dass Sie nur die Quadratwurzel der Zahl überprüfen müssen. Dies liegt daran, dass Faktoren paarweise vorkommen, wobei einer kleiner ist als die Quadratwurzel und der andere größer ist.
Eine Ausnahme ist, wenn n ein exaktes Quadrat ist, dann ist seine Quadratwurzel ein Faktor von n , aber kein Teil eines Paares.
Wenn Ihre Nummer beispielsweise 30 ist, sind die Faktoren in diesen Paaren:
Sie müssen also keine Zahlen höher als 5 überprüfen, da alle anderen Faktoren bereits abgeleitet werden können, sobald Sie den entsprechenden kleinen Faktor im Paar gefunden haben.
Hier ist eine Möglichkeit, dies in C # zu tun:
%Vor%Es gibt andere Ansätze, die Sie verwenden könnten, die schneller sind, aber Sie könnten feststellen, dass dies bereits schnell genug für Ihre Anforderungen ist, besonders wenn Sie nur mit 32-Bit-Ganzzahlen arbeiten müssen.
Reduzieren Sie die Grenze, wie hoch Sie gehen müssen, da Sie wissentlich bei der Quadratwurzel der Zahl stoppen können, obwohl dies die Vorsicht beim Auswählen von Quadraten mit der ungeraden Anzahl von Faktoren mit sich bringt, aber es hilft dabei, zu reduzieren Wie oft muss die Schleife ausgeführt werden.
Sieht so aus, als gäbe es eine ausführliche Diskussion über dieses genaue Thema hier: Algorithmus zur Berechnung der Anzahl der Teiler einer gegebenen Zahl
Hoffe, das hilft
Das erste, was zu bemerken ist, dass es ausreicht, alle Primfaktoren zu finden. Sobald Sie diese haben, ist es einfach, die Anzahl der gesamten Teiler zu finden: Für jede Primzahl addieren Sie 1 zu der Anzahl, wie oft sie erscheint und multiplizieren Sie diese zusammen. Also für 12 = 2 * 2 * 3 haben Sie (2 + 1) * (1 + 1) = 3 * 2 = 6 Faktoren.
Die nächste Sache folgt von der ersten: Wenn Sie einen Faktor finden, teilen Sie ihn so auf, dass die resultierende Zahl kleiner ist. Wenn Sie dies mit der Tatsache kombinieren, dass Sie nur die Quadratwurzel der aktuellen Zahl überprüfen müssen, ist dies eine große Verbesserung. Betrachten Sie zum Beispiel N = 10714293844487412. Naiv würde es N Schritte dauern. Die Überprüfung auf seine Quadratwurzel dauert sqrt (N) oder etwa 100 Millionen Schritte. Aber da die Faktoren 2, 2, 3 und 953 schon früh entdeckt werden, müssen Sie nur eine Million überprüfen - eine 100-fache Verbesserung!
Noch eine Verbesserung: Sie müssen nicht jede Zahl überprüfen, um zu sehen, ob sie Ihre Nummer teilt, nur die Primzahlen. Wenn es bequemer ist, können Sie 2 und die ungeraden Zahlen oder 2, 3 und die Zahlen 6n-1 und 6n + 1 (ein einfaches Radsieb) verwenden.
Hier ist noch eine nette Verbesserung. Wenn Sie schnell feststellen können, ob eine Zahl eine Primzahl ist, können Sie die Notwendigkeit für eine Division noch weiter reduzieren. Nehmen wir an, Sie haben nach dem Entfernen kleiner Faktoren 120528291333090808192969. Selbst die Überprüfung auf die Quadratwurzel wird eine lange Zeit dauern - 300 Milliarden Schritte. Aber ein Miller-Rabin-Test (sehr schnell - vielleicht 10 bis 20 Nanosekunden ) wird zeigen, dass diese Zahl zusammengesetzt ist. Wie hilft das? Es bedeutet, dass, wenn Sie die Kubikwurzel überprüfen und keine Faktoren finden, genau zwei Primzahlen übrig sind. Wenn die Zahl ein Quadrat ist, sind ihre Faktoren prim; Wenn die Zahl kein Quadrat ist, sind die Zahlen unterschiedliche Primzahlen. Das bedeutet, dass Sie Ihre "laufende Summe" um 3 oder 4 multiplizieren können, um die endgültige Antwort zu erhalten - auch ohne die Faktoren zu kennen! Dies kann einen größeren Unterschied machen, als Sie vermuten würden: Die Anzahl der erforderlichen Schritte sinkt von 300 Milliarden auf nur noch 50 Millionen - eine 6000-fache Verbesserung!
Das einzige Problem mit dem Obigen ist, dass Miller-Rabin nur beweisen kann, dass Zahlen zusammengesetzt sind; wenn es eine Primzahl erhält, kann es nicht beweisen, dass die Zahl Primzahl ist. In diesem Fall möchten Sie möglicherweise eine Primzahlprüfungsfunktion schreiben, um sich den Aufwand der Faktorisierung auf die Quadratwurzel der Zahl zu sparen. (Alternativ könnten Sie noch ein paar Miller-Rabin-Tests machen, wenn Sie mit der hohen Wahrscheinlichkeit zufrieden wären, dass Ihre Antwort richtig ist, und nicht als Beweis dafür. Wenn eine Zahl 15 Tests besteht, ist sie zusammengesetzt mit einer Wahrscheinlichkeit von weniger als 1 in einer Milliarde.)
Starten Sie Ihren Loop-Counter bei 2 (wenn Ihre Nummer gerade ist) oder 3 (bei ungeraden Werten). Dies sollte es Ihnen ermöglichen, jede zweite Zahl zu überprüfen, die Ihre Schleifenanzahl um weitere 50% verringert.
%Vor%Nun, wenn Sie diese Funktion sehr oft verwenden werden, können Sie den modifizierten Algorithmus von Eratosthenes Ссылка verwenden und die Antworten für diese speichern ein Intervall von 1 bis Max im Array. Es wird IntializeArray () einmal ausführen und danach Antworten in 0 (1) zurückgeben.
%Vor%Aber wenn Sie diese Funktion nicht oft verwenden werden, ist die beste Lösung, die Unitall-Quadratwurzel zu überprüfen.
Hinweis: Ich habe meinen Code korrigiert!
Ein einfach zu implementierender Algorithmus, der Sie viel weiter bringt als die Trial Division ist Pollard Rho
Hier ist eine Java-Implementierung, die sich leicht an C # anpassen lässt: Ссылка
Tags und Links c# math performance factors