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.

[jmit]

Hallo,

nettes Programm. Mach weiter so.

Ist das gewollt, das der Abbruchbutton keine Funktion hat.

Gruß Jörg

[Flare]

Also bei mir funktioniert der Abbruchbutton. Allerdings merkt man das ja erst bei zu großen Zahlen.
Und ein was: Du hscreibst, dass man beliebig große Zahlen nehmen kann, aber zum Beispiel für die Zahl 12345678901234567890 braucht er 0 (Milli)Sekunden, also sehr schnell. Jedoch für die Zahl 123456789012345678901 braucht er sehr sehr lange (nach 10 Sekunden über oben genannten Button abgebrochen). Da stimmt irgendetwas nicht würde ich sagen...


Flare

[Chewie]

@Flare: Klar kann das sein.

Die Quersumme von 12345678901234567890 ist 90, also durch 3 teilbar. Was das heißt, lernt man nicht erst in einer Vorlesung über Modulo-Arithmetik, sondern bereits in der Grundschule ;)

[Antigo]

Danke für das Feedback.

Es ist tatsächlich so, dass eine Zahl in Nullzeit berechnet werden kann. Und diese Zahl+1 ewigkeiten braucht. Das hängt einfach davon ab durch was sie teilbar ist. Ist sie direkt durch zwei teilbar. Ist die Zahl mit der man weiterrechnet nur noch halb so groß. Ist sie erst durch eine 4 oder 5 Stellige Zahl teilbar, muss diese erstmal gefunden werden ;)

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. Dann bricht er ab und deklariert die Zahl als Prim. Ich bin noch am Überlegen ob ich dass nicht abfangen sollte und die Zahl an sich erstmal überprüfen sollte, ob sie Prim ist...


Noch kurz zum Thema beliebig große Zahlen. Damit ist nur gemeint, das das Programm mit diesen zahlen "umgehen" kann. Das heisst nach endlich viel Zeit würde das Programm zu einem Ergebnis kommen. WIelange das ist, ist natürlich eine andere Frage ;)

edit: Ich sehe grade du hast die Zahl nicht nur um eins erhöht, sondern eine eins drangehangen, was den Wert der Zahl vertausendfacht und dadurch natürlich auch die Rechenzeit explodieren lässt.


Ich gucke mal ob ich so etwas wie einen Fortschrittsbalken bauen kann, der sagt welche Zahlen er schon probiert hat, und wieviele noch nicht. Dazu noch eine Zwischenspeicherfunktion und mann kann sich auch an größere Zahlen wagen ^^

[jfheins]

Zitat:

Zitat von Antigo

Ich bin noch am Überlegen ob ich dass nicht abfangen sollte und die Zahl an sich erstmal überprüfen sollte, ob sie Prim ist...

Machs liber nicht, denn ein zuverlässiger Primzahltest geht *zufällig* alle Zahlen durch, bis zur Hälfte Quadratwurzel ... das wäre dann ein wenig doppelt gemoppelt ;)
(Natürlich könnte man auch nur jede ungerade probieren, aber ... ihr wisst, was gemint ist ;) )

Zitat:

sondern eine eins drangehangen, was den Wert der Zahl vertausendfacht und dadurch natürlich auch die Rechenzeit explodieren lässt.

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

Das mit der Hälfte weis ich aber doch eigentlich :wall:
Ich habe mich halt am Autor des Zitats orientiert :stupid:

[Antigo]

äh jo :oops:
da ist es wohl mit mir durchgegangen. Aber mir fällt grad ein wie ich dadrauf gekommen bin. Wenn man an eine Zahl eine STelle dranhängt ist diese Zahl 1000% der alten Zahl. Das ist aber trotzdem "Nur" der Faktor 10 um den die Zahl größer wird. Trotzdem, je größer die Zahl an sich schon ist, desto extremer steigt die Mehr Belastung des Programmes wenn man eine STelle dranhängt. ISt logisch....

[marcelwhip]

bei delphi gibts doch diesen fortschrittsbalken
mit dem befehl "name.stepit" kannst du den balken um einen festgelegten wert wachsen lassen.
allerdings stell ich mir die realisierung problematisch vor, da wenn ich das programm richtig verstanden habe, die zeit sich nicht linear verhält, denn je kleiner die zahl, desto kürzer die berechnungsdauer..
oder bin ich aufm holzweg?

[fwsp]

niemand hat gesagt, dass der fortschritt linear visualisiert werden muss.
:???:

[marcelwhip]

schon gut, aber wen nervt das nicht, wenn bei der installation von programmen der balken ne halbe stunde bei 19% ist, und dann in 3 minuten auf hundert geht?!
und unsere uhren, jedenfalls meine^^ geht ziemlich linear, jedenfalls hoff ich das