Du verwendest einen veralteten Browser. Es ist möglich, dass diese oder andere Websites nicht korrekt angezeigt werden. Du solltest ein Upgrade durchführen oder einen alternativen Browser verwenden.
Wobei ich die Wurzel auch nur einmal berechnen würde und nicht bei jedem Schleifendurchgang... auch wenn es durchaus sein kann, dass es durch Compiler-/CPU-Optimierungen auch nur einmal berechnet wird.
Mein Vorschlag wäre ja,das ganze zu partitionieren.
1. Prinzahlen sind invariabel.
Ergo kann man bis zu einem festzulegenden n alle Primzahlen irgendwo festschreiben (preseed) oder in einem ersten Schritt ermitteln. Praktisch ergibt sich eine solche Obergrenze bereits aus dem nutzbaren Wertebereich mit max(Primzahl) <= sqrt(maximaler Input) zum einen und maxInput element (unsigned)int64.
2. Die Liste der so ermittelten Primzahlen ist insbesondere in Relation zur Gesamtmenge der möglichen (und zulässigen) Inputs minimal.
3. Infolgedessen läßt sich mein Kandidat i, für den ich einen Primzahlzerlegung haben will, per einfacher Iteration über die in (1) festgeschriebene Menge der Primzahlen ermitteln mit absteigender Ordnung, um erwarteten Aufwand zu sparen (da es keinen fixen Abstand zwischen den einzelnen Primzahlen gibt).
4. Insbesondere können wir den Vorgang rekursiv angehen: Jeder Input setzt sich notwendigerweise zusammen aus einer Primzahl (dh. der Faktor p steck in meinem Primzahl-Preseed) und einer Unbekannten, von der gesucht ist, ob diese denn eine Primzahl ist oder nicht.
5. Entsprechend erhalten wir eine Handlungsanweisung nach:
A übernehme Subrange des Primzahl-Preseeds von 2 bis zur größten Primzahl, die noch kleiner(oder gleich) srt(input) ist
B Führe ganzzahlige Division durch mit input DIV pz, angefangen mit der größten PZ aus (A) und nimm auch den Divisionsrest mit
C Brich ab wenn der Divisionsrest gleich 0 ist
D Gib die aktuelle PZ aus als Faktor und starte die Funktion mit dem Divisionsergebnis neu.
(Natürlich ist ein geeignetes Abbruchkriterum zu finden, damit meine 8 auch wirklich drei "2" auf den Bildschirm zeichnet; nicht weniger, aber auch nicht mehr.)
Ergebnisse sollten so signifikant schneller auf der Konsole landen.
Protip: niemals in einer Schleife irgendwas auf den Bildschirm zeichnen => verlangsamt den Ablauf signifikant.
Stattdessen das Ergebnis aufheben und nach der Schleife als Ganzes ausgegen.
@RalphS: Ich denke der TE wird für deine Ausführungen sehr froh sein. Ich denke, er war auf der Suche nach dem perfekten und optimiertesten Algorithmus für das Problem.
Warum eigentlich mit der größten Primzahl anfangen in (B)? Welchen Unterschied macht es aus deiner Sicht, ob man mit der kleinsten oder der größten Primzahl anfängt? Spart man sich damit Arbeit?
Okay, die Verarbeitungsrichtung der PZ ist sicherlich eher uninteressant. Ansatz war da, daß ich weniger PZ angucken muß. Aber natürlich gibt es trotzdem nur eine fixe Anzahl PZ zum anschauen und das sind wenige, sodaß dies wenn überhaupt kaum ins Gewicht fällt.
Ich ganz persönlich halte das Sieb in der Programmierung für suboptimal- zumindest auf heimischen PCs - wegen des in Abhängigkeit der größten gesuchten PZ quadratischen Speicherbedarfs. Da kann man iterativ vorgehen und sich einfach die gefundenen PZ merken - nicht alles was die Mathematik optimal nennt, ist auch für die Informatik optimal.
Aber der Einwand war vermutlich nicht ganz ernst gemeint, im Hinblick auf das NFS — das braucht zuhause keiner und es wird dort wohl auch nicht viele Ergebnisse liefern.
