Javascript
 

 Primfaktoren berechnen

Auf dieser Seite können Sie sich die Primfaktorzerlegung ganzer Zahlen darstellen lassen:

Minimum:
Maximum:

Beschreibung

Das Javascript-Programm berechnet als erstes alle Primzahlen bis zur Hälfte des eingegebenen Maximalwerts und speichert sie in einem Array. (Bis zur Hälfte deswegen, weil der Primfaktor einer Zahl einen Faktor braucht, mit dem multipliziert er wieder die Zahl ergibt. Der kleinstmögliche Faktor ist 2.)

Die Primzahlberechnung erfolgt durch Probieren:
Eine Zahl wird so lange durch alle Zahlen von 2 bis zur Wurzel der Zahl (bzw. der nächstkleineren ganzen Zahl) geteilt, bis eine dieser Divisionen den Rest Null ergibt. Dann ist es keine Primzahl. In diesem Fall wird die nächste Zahl auf Primzahl untersucht.
Hatten am Ende alle Divisionen einen Rest, gab es keinen echten Teiler, die Zahl ist also eine Primzahl und wird in das Array geschrieben.
Das Probieren braucht deshalb jeweils nur bis zur Wurzel der Zahl zu gehen, weil der kleinste Teiler einer Zahl - wenn sie denn einen hat - immer kleiner oder höchstens gleich der Wurzel dieser Zahl ist.
Das kann man sich leicht überlegen, denn jeder Teiler muss einen "Partner" haben, mit dem multiplitiert er wieder die Zahl ergibt.
Beispiel: 36
36 = 2 * 18
36 = 4 * 9
36 = 6 * 6
Einer dieser "Partner" ist immer kleiner und einer immer größer als die Wurzel der Zahl; die Wurzel ist, wenn sie ganzzahlig ist, ihr eigener Partner. Quadratzahlen sind deshalb die einzigen Zahlen, die eine ungerade Anzahl von Teilern besitzen.

Weiter zum Programmablauf:
Liegen die Primzahlen im Array vor, werden sie zunächst in einem neuen Dokument ausgegeben, damit diese aufwändige Rechnung sich auch in der Ausgabe niederschlägt.

Anschließend wird jede ganze Zahl von Minimum bis Maximum der Reihe nach durch alle Elemente des Arrays, also durch alle Primzahlen geteilt.
Ist eine der probierten Primzahlen ein Teiler der Zahl, wird er in die Ausgabe geschrieben.
Der Quotient wird mit der zuletzt verwendeten Primzahl erneut untersucht, weil es bei der Primfaktorzerlegung ja vorkommen kann, dass eine Primzahl mehrfacher Teiler einer Zahl ist.
Beispiel: 525 = 3 * 5 * 5 * 7
Ergibt die Division 1, ist der Algorithmus beendet, denn in diesem Fall ist die untersuchte Zahl bzw. der weiter untersuchte Quotient selbst eine Primzahl und hat keine weiteren Teiler mehr.

Am Ende wird noch die Laufzeit berechnet und ausgegeben.

Das Programm hat bei größeren Zahlen eine so große Laufzeit, dass der Internet Explorer ungeduldig wird, und fragt, ob er das Skript abbrechen soll.
Deshalb wollte ich die Laufzeit optimieren und verfiel auf folgende Idee:
Man könnte doch, anstatt zu Beginn alle Primzahlen bis zum eingegebenen Maximum zu berechnen, die Primfaktorzerlegung selbst dazu benutzen, die erforderlichen Primzahlen zu ermitteln. Immer wenn man bei einer Primfaktorzerlegung mehr Primzahlen braucht, als im Primzahlarray vorhanden ist, ist der Rest der Faktorzerlegung eine weitere Primzahl, die man nur noch speichern muss!
Das hat die Laufzeit-Vorteile, dass u.U. weniger Primzahlen bestimmt werden müssen (weil für die Faktorzerlegung vielleicht gar nicht alle gebraucht werden, die sonst auf Vorrat bestimmt werden), dass weniger Zahlen darauf getestet werden müssen, ob es sich um eine Primzahl handelt, dass der Test auf Primzahleigenschaft mit weniger Divisionen auskommt, weil nur noch durch die schon bekannten Primzahlen geteilt wird, anstatt durch alle Zahlen, und dass die Divisionen zur Primzahlermittlung ohnehin für die Faktorzerlegung durchgeführt werden, die Primzahleigenschaft also quasi ein Abfallprodukt ist.
Nachteil bei der neuen Variante ist, dass die Faktorzerlegung für jede Zahl bis zum Ende erfolgen muss, und nicht bei der Wurzel der Zahl oder beim ersten auftretenden Teiler beendet werden kann, weil man sonst Primzahlen verpasst. Auch die Zahlen, die kleiner sind als das eingegebene Minimum, müssen in Primfaktoren zerlegt werden, obwohl man deren Faktordarstellung in der Ausgabe gar nicht braucht.

Das Ergebnis war jedenfalls, dass das neue Programm NOCH langsamer war als dieses hier:
Bei Minimum = 1.000 und Maximum = 1.100 brauchte es 172 statt 78msec.
Bei Minimum = 10.000 und Maximum = 10.100 brauchte es sogar 6.484.234 statt 391msec.

Eine andere Verbesserung sollte die Umstellung auf den Algorithmus "Sieb des Eratosthenes" sein.
Meine Implementierung war allerdings noch langsamer als obige Probiermethode. Das mag an der Art der Speicherung gelegen haben, weil man anfangs ja alle (ungeraden) Zahlen speichert und sie erst nach und nach löscht.
Arndt Brünner hat eine bessere Implementierung gefunden, die ich hier so geändert habe, dass sie genau so eine neue Internetseite erzeugt wie das andere Programm.

Hier können Sie eine Zip-Datei (13MB!) mit allen Primzahlen bis 100Millionen laden!




Home
Falls diese Seite ohne Navigationsleiste angezeigt wird, aktivieren Sie Javascript oder klicken Sie hier!