Teiler von grossen Zahlen ermitteln
Hallo Leute
Mathe-Frage: Wie ermittle ich am effizientesten alle Teiler einer grossen Zahl, z.B. von 625?
Bei kleineren Zahlen ermittle ich alle Teiler bis zur Hälfte der Zahl, in diesem Beispiel bis ca. 312 und wende dann das Prinzip des Komplementärteilers an, dann habe ich alle Teiler. Aber das dauert bei grossen Zahlen viel zu lange! Ich verstehe die Primzahlfaktor-Ermittlung. Checke aber noch nicht wie mir das helfen soll auch jene Teiler zu ermitteln, die eben keine Primzahlen sind!
Dankeeeee für eure Hilfe ;)
Rebecca
4 Antworten
-
Du brauchst nicht bis zur Hälfte der Zahl zu probieren! Es reicht, wenn Du bis zur Wurzel gehst, bei 625 also bis 25: Wenn Du einen neuen, größeren Teiler findest, wird der Komplementärteiler kleiner als der des vorhergehenden Teilers. Für die Wurzel ist der Komplementärteiler eben wieder die Wurzel, für jeden größeren Teiler müsste dann der Komplementärteiler kleiner als die Wurzel sein, wäre also schon vorher als "normaler" Teiler aufgefallen.
-
Alle Teiler, die keine Primzahlen sind, ergeben sich aus den möglichen verschiedenen Produkten der Primzahlteiler. Beispiel: Die Primzahlzerlegung von 12 ist 2 * 2 * 3, die nicht-primen Teiler sind dann 2 * 2 = 4 und 2 * 3 = 6. Für 625 ist die Primzahlzerlegung 5 * 5 * 5 * 5 , die nicht-primen Teiler sind dann 5 * 5 = 25 und 5 * 5 * 5 = 125. (Hinzu kommen natürlich immer 1 und die Zahl selbst.)
Doch, jede Zahl hat eine Wurzel, nur ist das für die meisten Zahlen keine ganze Zahl, die meisten Wurzeln sind irrationale Zahlen (d. h. sie haben unendlich viele Stellen nach dem Komma, ohne Periode).
Beispiele:
- Wurzel(2) = 1,414...
- Wurzel(5) = 2,236...
- Wurzel(10) = 3,162...
- Wurzel(20) = 4,472...
- Wurzel(50) = 7,071...
- Wurzel(120) = 10,954...
(Da wo die ... stehen, kommen immer noch unendlich viele weitere Stellen, die kann ich aber eben nicht alle hinschreiben.)
Wenn Du also jetzt z. B. die Teiler von 50 ermitteln willst, brauchst Du nur bis 7 zu suchen (damit 8 ein Teiler sein könnte, müsste der Komplementärteiler kleiner als 7,071... sein). Du brauchst die Wurzeln aber auch gar nicht genau zu berechnen, es reicht, wenn Du schaust, was die nächst kleiner Quadratzahl ist, und dann bis zu deren Wurzel probierst. Wenn Du also z. B. die Teiler von 120 bestimmen willst, kannst Du Dir überlegen, dass 10 * 10 = 100 < 120 und11 * 11 = 121 > 120 ist, es reicht also, bis 10 zu suchen.
Du musst alle Primzahlen ausprobieren bis maximal der Wurzel aus der Zahl, hier also 25.
Alle anderen Teiler sind dann Produkte aus diesen Primzahlen.
Du musst nicht bis zur Hälfte der Zahl, sondern maximal bis zur Wurzel testen. Dadurch bekommst du dann die Primfaktorzerlegung. Nimm mal
625
Die Wurzel davon ist dann 25.
Ich fange also an, die Zahlen zu testen: 2, 3 -> kein Teiler.
5 -> Teiler, also
625 = 5 * 125
Jetzt kümmer ich mich nur noch um 125 (maximal bis 12, denn 12² ist schon größer):
2 und 3 sind keine Teiler, das weiß ich schon. 5 ist wieder ein Teiler:
625 = 5 * 5 * 25
Das brauche ich nun nicht mehr weiterzumachen, ich sehe jetzt gleich:
625 = 5^4.
Die Teiler von 625 sind dann alle möglichen Kombinationen aus den Primzahlpotenzen. Das ist hier einfach, weil es nur eine einzige Primzahl gibt:
Teiler von 625 = {1, 5^1, 5², 5³, 5^4}
Anderes Beispiel: 144
Zerlegt in Primzahlen:
2^4 * 3³
Alle Kombinationen:
2^0 * 3^0 = 1
2^1 * 3^0 = 2
2^2 * 3^0 = 4
2^3 * 3^0 = 8
2^4 * 3^0 = 16
2^0 * 3^1 = 3
2^1 * 3^1 = 6
2^2 * 3^1 = 12
2^3 * 3^1 = 24
2^4 * 3^1 = 48
2^0 * 3^2 = 9
2^1 * 3^2 = 18
2^2 * 3^2 = 36
2^3 * 3^2 = 72
2^4 * 3^2 = 144
Teiler von 144 = {1,2,4,8,16, 3,6,12,24,48,9,18, 36, 72, 144}
Aus der Primfaktorzerlegung kannst du durch Kombination der einzelnen Primfaktorpotenzen alle Teiler ermitteln.
"Am effizientesten" Ist eine schwere Frage, es ist nicht bekannt wie schnell der schnellste Algorithmus ist, falls es einen "schnellsten" gibt. Wenn du gut in Informatik bist, kannst du dich hieran versuchen, damit kannst du die meisten Zahlen relativ schnell faktorisieren können, mit denen du arbeiten musst:
Ich versteh das nicht. Du sagst ich muss nur bis zur Wurzel rechnen. Aber nicht jede Zahl hat eine Wurzel?! 625 schon, aber 120 z.B. nicht.