Faktorisierung

[Antigo]

Hi,
Ich habe ein kleines Programm zu Faktorisierung von beliebigen Zahlen geschrieben.

Faktorisierung bedeutet, dass man eine Zahl als ein Produkt von Primzahlen darstellt. Diese Primzahlfaktoren werden aufsteigend asugegeben. Dadurch ist diese Darstellung für jede Zahl eindeutig.

Beispiel:
Zahl 6 ist 2 * 3. DIe Zahlen 2 und 3 sind hier die Primzahlen aus denen sich die Zahl 6 zusammensetzt.

oder
Die Zahl 2145 ist 3 * 5 * 11 * 13.

Kommt ein Faktor zweimal vor, wird er als Exponent dargestellt. 8 ist beispielsweise 2 * 2 * 2. Es wird jedoch als 2^3 ausgegeben.


Alles weitere ist angehangen



edit:
~~~~~~~~~~~~~~~~~~~~~~Update~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~
Dank der Hilfe von vielen DP Mitgliedern, konnte ich das Programm um einiges schneller machen. Zum direkten Vergleich lasse ich das alte Programm auch angehangen.

Was jetzt noch fehlt:
Zum einen ein Statusbalken, der anzeigt, wieweit man in der Berechnung berets fortgeschritten ist. Das hat auf Anhieb nicht hingehauen so wie ich das wollte. Also muss ich mir nochmal Gedanken machen.
Zum anderen gibt es noch zwei drei Bugs die ich noch beheben muss. Die Zahlen 6,9,15,21 werden fälschlicherweise als Primzahl angegeben. Jensseits der 20er Marke scheint jedoch alles zu funktionieren. Notfall werde ich diese Zahlen als Sonderfälle behandeln.

[Antigo]

Also man kann mit Sicherheit keinen vernünftigen Statusbalken bauen, der gleichmässig von 0 bis 100% geht. Dafür müsste man vorher schon wissen, wieviele Teiler die Zahl hat und welche das sind ^^

Aber zumindest kann man angeben wieviele Zahlen schon getestet wurden und wieviele noch übrig sind. So das man ungefähr abschätzen kann wieweit man in der Berechnung ist. DIe Frage ist nur inwiefern das auf die Performance schlägt wenn man den Status der Berechnung ständig ausgeben lässt... Müsste man mal ausprobieren.

[Chewie]

Wenn man bei jedem Schritt den Balken aktualisiert, dann ja, das würde es lange verzögern.
Aber wenn mans bei jedem 100. oder so macht macht es wenig aus.

[Khabarakh]

Zitat von Antigo:

Am längsten dauern übrigens Primzahlen, da das Programm solange Teiler sucht, bis der Teiler den er ausprobiert größer ist als die Hälfte der Zahl.

Zitat von jfheins:

Machs liber nicht, denn ein zuverlässiger Primzahltest geht *zufällig* alle Zahlen durch, bis zur Hälfte ...

Was habt ihr denn mit eurer Hälfte ? Ein Test bis zur Quadratwurzel reicht vollkommen.

[Cöster]

Zitat von Antigo:

Am längsten dauern übrigens Primzahlen, da das Programm solange Teiler sucht, bis der Teiler den er ausprobiert größer ist als die Hälfte der Zahl.

Es reicht doch, wenn du so lange ausprobierst, bis der Teiler größer ist als die Wurzel der Zahl.

Beispiel:
Die Zahl lautet 53, Wurzel ist also zwischen 7 und 8. Du versuchst einfach 2, 3, 5, 7 (du solltest die unteren Primzahlen in einem Array speichern, damit du Zahlen wie 4 oder 6 gar nicht erst ausprobieren musst), die nächste Zahl wäre 11, liegt also über der Wurzel und du brauchst sie gar nicht mehr auszuprobieren, da der andere Teiler dann ja kleiner als die Wurzel wäre, aber die hast du ja schon alle ausprobiert.

Außerdem solltest du rekursiv rechnen (vielleicht machst du das ja auch schon). Dann müsstest du bei z.B. 100 nur 6 mal probieren:
100/2 -> 50
50/2 -> 25
25/2 -> geht nicht
25/3 -> geht nicht
25/5 -> 5 //jetzt nicht wieder die Zahlen kleiner als 5 ausprobieren, die hast du ja schon alle getestet
5/5 -> 1 fertig

Wenn du nach 100/2 allerdings weiterprobieren würdest mit 100/3, müsstest du wirklich bis 50 durchprobieren. Das bedeutete ein Vielfaches des Rechenaufwandes. Wie soll das dann erst bei größeren Zahlen sein?

[Antigo]

Also beim Primzahltest ist es klar das ich nur bis zur Wurzel gehen muss. Hier gehe ich ja so vor, das ich die Zahl durch alle Zahlen teile (natürlich nur wenn die Zahl keine 0,2,4,6,8 oder 5 am Ende hat; und eben auch nur bis zur Wurzel der Zahl) und gucke ob ein Rest übig ist. Ist bei einer einzigen Division kein Rest übrig (zahl mod i =0) ist die Zahl keine Primzahl.

Bei der Faktorisierung ist das allerdings anders. Hier muss ich bis zur Hälfte durchgehen.
Ich gehe ja folgendermassen vor (Methode 2/Methode 3), dass ich die Zahl durch alle Zahlen teile und nach einem ganzzahligen Teiler suche (wiederum zahl mod i = 0). Habe ich einen gefunden, überprüfe ich ob dieser Teiler auch eine Primzahl ist, wenn nicht, dann gehts weiter mit dem nächsten Teiler den ich finde. Ich kann hier erst sicher sein, dass ich keinen ganzzahligen Teiler der Zahl finde, wenn ich bis zur Hälfte der Zahl alle Zahlen die diese teilen auf Prim überprüft habe. Wenn ich hier schon nach der Wurzel der Zahl aufhöre, sind plötzlich alle Zahlen prim


Zum rekursiven. Ich habe es so programmiert wie du es geschrieben hast. Allerdings hat das bei mir nichts mit rekursiv zu tun Ich gehe einfach eine Schleife durch, also iterativ (so heisst das gegenteil glaub ich ^^)

[Khabarakh]

Zitat von Antigo:

Bei der Faktorisierung ist das allerdings anders. Hier muss ich bis zur Hälfte durchgehen.
Ich gehe ja folgendermassen vor (Methode 2/Methode 3), dass ich die Zahl durch alle Zahlen teile und nach einem ganzzahligen Teiler suche (wiederum zahl mod i = 0). Habe ich einen gefunden, überprüfe ich ob dieser Teiler auch eine Primzahl ist, [...]

Wozu denn das ? Wenn du den zu testenden Teiler schrittweise erhöhst, muss der erste Treffer auch eine Primzahl sein.

[negaH]

Zitat:

Nana, bleib' mal auf Boden ... hinten eine Stelle mehr sollte (im Dezimalsystem) die Zahl höchstens ver19fachenb, aber nicht 1000

du meinst ver-10-fachen oder ?

Je nach Wertebereich der zu faktorisierenden Zahl wird man mit unterschiedlichen Verfahren arbeiten müssen.

Hat man zb. eine Liste aller kleinen Primzahlen bis 2^32 so kann man logischerweise nur Zahlen bis 2^64 damit per Trial Division testen.

Gruß Hagen

[Antigo]

Das war der erste Ansatz den ich verfolgt hatte (Methode 1). Ich hab die Zahl einfach durch alle Primzahlen geteilt die kleiner gleich der Hälfte der Zahl waren. Dafür musste ich aber bei großen Zahlen mehrere hunderttausend Primzahlen errechnen, was einfach unglaublich viel Rechenzeit kostet.

Besser funktioniert es andersrum(Methode2+3). Jetzt suche ich nicht mehr nach einer Primzahl die gleichzeitig Teiler der Zahl ist, sondern nach einem Teiler der Zahl der gleichzeitig Primzahl ist. Dadurch muss ich unfassbar weniger Primzahlen berechnen als vorher.

edit: das ging an Khabarakh

[Khabarakh]

Zitat von Antigo:

Besser funktioniert es andersrum(Methode2+3). Jetzt suche ich nicht mehr nach einer Primzahl die gleichzeitig Teiler der Zahl ist, sondern nach einem Teiler der Zahl der gleichzeitig Primzahl ist. Dadurch muss ich unfassbar weniger Primzahlen berechnen als vorher.

Hmm, kannst du deine Vorgehensweise noch etwas ausführen? Die Möglichkeit zum Selbst Nachschauen ist ja leider nicht gegeben .

[Cöster]

Zitat von Khabarakh:

Zitat von Antigo:

Bei der Faktorisierung ist das allerdings anders. Hier muss ich bis zur Hälfte durchgehen.
Ich gehe ja folgendermassen vor (Methode 2/Methode 3), dass ich die Zahl durch alle Zahlen teile und nach einem ganzzahligen Teiler suche (wiederum zahl mod i = 0). Habe ich einen gefunden, überprüfe ich ob dieser Teiler auch eine Primzahl ist, [...]

Wozu denn das ? Wenn du den zu testenden Teiler schrittweise erhöhst, muss der erste Treffer auch eine Primzahl sein.

Ganz genau! Wenn du es nämlich so machst, wie ich es beschrieben hab, wird die Zahl, ja nie durch z.B. 4 teilbar sein. Wenn doch, wäre sie ja bereits bei der 2 geteilt worden und diese Zahl wird nicht weiter überprüft, sondern nur noch die Hälfte dieser Zahl (100 teilst du nie durch 4 sondern erst durch 2, dann hast du ja nur noch 50 und die lässt sich dann nicht mehr durch 4 teilen). Wenn man also (nach meinem Verfahren) einen möglichen Teiler findet, ist er immer eine Primzahl.