 |
 |
 |
 |
 |
 |
Startseite » Forum » Produkt in Faktoren zerlegen.
Produkt in Faktoren zerlegen.
Universität / Fachhochschule
Tags: einfach, Faktor, MATH, Multiplikation, produkt
 
|
  |
|---|
|
Hallo Leute, seid einiger Zeit beschäftige ich mich mit der Frage, wie ein Algorithmus aussehen könnte in der man es schafft, ein Produkt in seine Faktoren zu zerlegen. Bsp. hat man aber nur die als Zahl da stehen und weiß, dass es ein Produkt von oder beliebigen Faktoren ist, so hat man ein großes Problem. Dann gibt es eigentlich etliche Möglichkeiten. Ist dieses Problem nur durch Probieren zu lösen oder geht das auch anders? Vllt bin ich nicht der erste, der sich mit dieser Fragestellung beschäftigt. Würde mich über jede Hilfestellung freuen, Gruß Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert): "Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen." |
| Hierzu passend bei OnlineMathe: Online-Übungen (Übungsaufgaben) bei unterricht.de: |
|
 |
|
Durch Probieren - nun ja - ich würde sagen durch geschicktes Probieren. Sinnvoll ist ja wohl nur die Aufgabe, die Zahl in alle ihre Primfaktoren zu zerlegen, also in deinem Beispiel . Am schnellsten geht es wohl, wenn dein Programm auf eine möglichst lange Liste von Primzahlen zurückgreifen kann oder sich diese bei Programmstart erzeugt. Dann gehst du diese Liste einfach durch und versuchst, deine Zahl durch diese Primzahlen (restlos) zu teilen. Wie das konkret realisiert wird hängt von der verwendeten Programmiersprache und den dort gebotenen Möglichkeiten ab. Beispielsweise kann es eine Modulo Funktion geben (so wie oder du vergleichst ob 1.0*z/p=("int)(z/p) ist, oder . (die Anführungsstriche gehören weg, aber sonst wird hier ein Integralzeichen daraus). Im Falle von hast du bei der ersten bereits Glück. Also teilst du und erhältst. . Das Ganze nochmals - wieder Glück mit 2. Also sind wir schon bei . UNd nochmals durch 2 und dann nochmals . Jetzt geht es nicht mehr durch 2 und wir müssen auch später nie wieder mehr unser Glück mit 2 versuchen. also die nächste Zahl in der Liste und die ist 3. etc. Es sollte klar sein, dass man es nur mit den Primzahlen bis Quadratwurzel aus der betrachteten Zahl versuchen muss. Also bei nur mit den sieben Primzahlen von 2 bis . Danach ist klar, dass nicht weiter zerlegbar ist. Steht keine Primzahlliste zur Verfügung und möchte man sich nicht die Mühe machen, eine solche automatisch erzeugen zu lassen, dann beginnt man eben mit dann 3 und alle weiteren ungeraden Zahlen - kostet eben ein wenig mehr Rechenzeit. Gruß |
|
|
|
Wenn man seinen Rechner "schlauer" suchen lassen möchte, kann man ja die üblichen Teilbarkeitseigenschaften noch abfragen. Wobei ich ziemlich sicher bin, dass das keinen Rechenzeitvorteil bringen dürfte. Helfen tut da ja ohnehin nur bei den kleineren Primzahlen. |
|
|
|
Hallo kommt daruaf an, wozu du die Zerlegung brauchst, um etwa den ggT von 2 Zahlen zu finden , gibt es einfachere bzw kürzere Methoden. gruß ledum |
 |
|
Erstmal bedanke ich mich für die Antworte. Roman hat den Nagel auf den Kopf getroffen, ich wollte ein Programm schreiben, dass sich mein Problem mit der zufällig gewählten Zahl in jede andere Zahl übertragen lässt. @Roman Auf das bin ich noch nicht gekommen, ich hatte als Ansatz erstmal gedacht, dass ich die Quersummen benutzen kann. Quersumme daraus folgt durch 3 teilbar. Quersumme teilbar Dadurch hätte ich was auf deine Lösung mit darum geht es mir aber nicht, das Programm soll am Ende so aussehen, dass ich möglichst alle Faktoren (dabei erstmal nur mit natürlichen positiven Zahlen und zwei faktoren) erhalte die zum Ergebnis führen. Bedeutet im Beispiel das mir das Programm am Ende sagt, usw. Das hätte ganz am Ende den Vorteil, dass ich bei mir zufällig gegebenen Zahlen schnell ein Algorithmus dahinter sehen könnte, wenn es einen gibt. Und ich Programmiere mit C. Ich komme mit dem Editor noch nicht so ganz klar, wenn das nicht verständlich ist kann ich das nochmal erklären. Gruß, Faith |
|
|
|
Dass du nicht nur 144 faktorisieren möchtest war mir schon klar, darum habe ich dir auch einen Algorithmus skizziert, der für beliebige natürliche Zahlen sein Werk vollbringt. Die Idee mit der Quersumme ist nicht zielführend, da du damit ja bloß die Teilbarkeit durch 3 zeigen kannst. Da gehts vermutlich mit Modulo genau so schnell. Und sonst wirst du nicht allzu viele Teilbarkeitsregeln auf Lager haben, fürchte ich. Vielleicht noch durch 2, wenn die letzte Ziffer gerade ist, durch 5 wenn die letzte Ziffer durch 5 teilbar ist, durch 11 mit der alternierenden Ziffernsumme - aber dann sind wir vermutlich schon am Ende der Weisheit angelangt. Ausprobieren bis zu einer vernünftigen Obergrenze (Wurzel) und die Zahl der Versuche minimieren (nur durch Primzahlen oder wenigsten nur durch ungerade Zahlen ,...) ist das schon der Weg, den du gehen solltest. Du müsstest dann noch austesten, welche Methode zur Feststellung der Teilbarkeit am schnellsten funktioniert, würde aber vermuten, das die Modulo-Funktion meist recht effizient implementiert ist, also ein if (z % n == 0) ... oder eine entsprechend negierte Laufbedingung in einer fußgesteuerten Schleife ganz gut ihren Dienst versehen werden. Bedeuten deine etwas unklaren Ausführungen (und das liegt nicht am Editor), dass du nicht (nur) die Primfaktorzerlegung einer Zahl suchst, sondern sämtliche unterschiedliche Zerlegungen in ein Produkt von 2 oder mehr Faktoren? Darf ich fragen, wozu? Eine Anmerkung noch: Ein wirklich effizientes Verfahren, um Zahlen (auch sehr große) schnell zu faktorisieren, gibt es derzeit (noch) nicht. Zumindest ist noch kein derartiges Verfahren veröffentlicht worden. Das ist auch der einzige Grund, warum derzeit das RSA Verschlüsselungsverfahren mit großer Schlüssellänge als relativ sicher gilt. Dort werden, vereinfacht ausgedrückt, zwei riesengroße Primzahlen miteinander multipliziert und das Ergebnis stellt im Wesentlichen den öffentlichen, allen bekannten Schlüssel dar. Eine der beiden Ausgangsprimzahlen ist i.W. der private Schlüssel. Wer in der Lage ist, das große Primzahlprodukt in seine beiden Primfaktoren zu zerlegen, hätte den Code geknackt. natürlich ist es möglich und es gibt auch schon eine ganze Reihe sehr raffinierter Methoden dazu, die weit über das von mir skizzierte Verfahren mit Probedivision hinausgehen. Das Thema ist auch immer wieder sehr beliebt bei Verschwörungstheoretikern. Da wird gern einmal behaupten, die Geheimdienste hätten längst DEN einen genialen Algorithmus in Händen, der jede noch so große Zahl in null-komma-nix faktorisiert. Oder man liest, die NSA hätte schon längst einen funktionierenden Prototyp eines Quantencomputers und würde damit mit Hilfe des Shor-Algorithmus (den gibts allerdings wirklich) bereits jede RSA-verschlüsselte Kommunikation knacken. Möge jeder glauben, was immer er will ;-) Gruß R |
 |
|
Du hast das schon richtig verstanden, ich will das in alle Faktoren zerlegen. Es gibt bereits Quantencomputer, von IBM wurde doch einer gezeigt. Jedenfalls war dein Ansatz hilfreich dafür bedanke ich mich, ich überlege mal ein wenig, das muss weiter vereinfachbar sein. Sollte ich weitere Ideen haben kann ich sie mit dir gerne teilen. |
1226901
1226624