Nun meine Frage: Die Primfaktorzerlegung nach Variante 1 beim ggT ist mir völlig klar, nur ich weiss nicht bei Variante 2, wie ich auf den Exponenten kommen soll ? Bei 36 und 64 ist das noch relativ einfach, aber was ist, wenn ich größere Zahlen wie 484 habe ? Wie komme ich da auf die Exponenten der Primzahlen ?
bewinol2013-12-30T01:56:31Z
Beste Antwort
Was du da bei 1) machst, ist keine PFZ sondern der Euklidsche Algorithmus für den GGT. PFZ sähe so aus:
948 = 2*474 = 2^2*237 --> 2*2*3*79
225 = 3*75 = 3*3*25 --> 3*3*5*5
Jetzt nachschauen, welche Primzahlen in beiden Zerlegungen vorkommen, hier nur eine 3.
Nun zu deiner Schlussfrage: Da geht man schrittweise vor:
i. Zahl = Ausgangszahl Teiler= erste Primzahl (= 2) ii. ist Zahl durch Teiler teilbar? iii-ja Teiler notieren Zahl = Zahl/Teiler goto ii. iII-nein . Teiler = nächste Primzahl ist Teiler = Zahl? iv-ja Teiler notieren ENDE iv-nein Teiler = nächste Primzahl goto ii
Die Primzahlzerlegung beginnt mit der kleinsten Primzahl (2) und wird solange dividiert bis nicht mehr teilbar ist. Dann wird mit der nächsten Primzahl weitergemacht.
Primzahlen: 2, 3, 5, 7, 11, 13, 17, 19, usw.
Selbst für groÃe Zahlen wird diese Methode verwendet. Die gröÃte Primzahl, die überprüft werden muss, ist kleiner als die Wurzel des Teilergebnisses.
z.B. 97 (Primzahl) 97 / 2 nicht teilbar 97 / 3 nicht teilbar 97 / 5 nicht teilbar 97 / 7 nicht teilbar
Da Wurzel(97) < 11 ist braucht man hier nicht weiterrrechnen und weià dass 97 eine Primzahl ist.
Ich versuche immer die Primfaktorzerlegung in kleinere Primfaktorzerlegungen aufzuteilen, denn die Primfaktorzerlegung von x = s * t ist ja die Primfaktorzerlegung von s * die Primfaktorzerlegung von t.
In diesem Fall sehe ich z. B. sofort, dass 484 durch 4 teilbar ist. Also weià ich, dass die Primfaktorzerlegun von 484 gleich die Primfaktorzerlegung von 4 und die Primfaktorzerlegung von 484 / 4 = 121 sind. Die Primfaktorzerlegung von 4 sind offensichtlich 2 * 2 und die von 121 11 * 11. Die Primfaktorzerlegung von 484 ist also 2 * 2 * 11 * 11 und das ist 2^2 * 11^2.