Primzahlrechner und Primfaktorzerlegung
Dieser Rechner erledigt zwei Dinge gleichzeitig: Er sagt Ihnen, ob eine ganze Zahl prim ist, und er zerlegt diese Zahl in ihre Primfaktoren, während Sie tippen. Eine Primzahl ist eine ganze Zahl größer als 1, deren einzige Teiler 1 und sie selbst sind — wie 2, 3, 5, 7 und 11. Jede Zahl, die nicht prim ist (eine zusammengesetzte Zahl), lässt sich als eindeutiges Produkt von Primfaktoren schreiben, was die Grundlage weiter Teile der Zahlentheorie und der in der Kryptographie verwendeten Algorithmen ist.
Ist sie prim?
Primfaktoren
Eine Primzahl ist nur durch 1 und sich selbst teilbar. Die Zerlegung zeigt die miteinander multiplizierten Primfaktoren.
Publicidad
So funktioniert es
Um zu prüfen, ob eine Zahl n prim ist, behandelt der Rechner die kleinen Fälle (Zahlen unter 2 sind nie prim, 2 und 3 sind prim) und versucht dann, n durch jede ungerade Zahl von 3 bis zur Quadratwurzel von n zu teilen. Teilt eine davon n genau, ist n zusammengesetzt; teilt keine, ist n prim. Es genügt, bis zur Quadratwurzel zu testen, denn hätte n einen Teiler größer als seine Wurzel, gäbe es auch einen zugehörigen kleineren. Für die Zerlegung teilt der Rechner wiederholt den kleinstmöglichen Faktor heraus: Er teilt durch 2, solange es geht, dann durch 3, dann durch 5 und so weiter und sammelt jeden Faktor, bis nichts übrig bleibt. Für 60 ergibt das 2 × 2 × 3 × 5, und für eine Primzahl wie 97 ist der einzige Faktor die 97 selbst.
Die Primzahlen bis 100
Zwischen 1 und 100 gibt es genau 25 Primzahlen. Die 2 ist die einzige gerade Primzahl: Jede andere gerade Zahl ist durch 2 teilbar, sodass ab da alle Primzahlen ungerade sind (auch wenn nicht jede ungerade Zahl prim ist, etwa 9 = 3 × 3 oder 15 = 3 × 5). Ein klassisches Verfahren, sie zu finden, ist das Sieb des Eratosthenes: Man schreibt die Zahlen ab 2 auf und streicht die Vielfachen jeder Primzahl (die von 2, dann von 3, von 5…); was ungestrichen bleibt, ist prim. Hier ist die vollständige Liste bis 100.
| Bereich | Primzahlen |
|---|---|
| 1 – 50 | 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 |
| 51 – 100 | 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 |
Wie man von Hand prüft, ob eine Zahl prim ist
Um zu prüfen, ob eine Zahl n prim ist, genügt es zu testen, ob eine Zahl von 2 bis zur Quadratwurzel von n sie teilt. Teilt keine sie genau, ist n prim. Zum Beispiel ist die Quadratwurzel von 97 etwa 9,85, man muss also nur 2, 3, 5 und 7 testen: Da keine davon teilt, ist 97 prim. 91 wirkt dagegen auf den ersten Blick prim, aber 91 = 7 × 13, also ist es zusammengesetzt. Nur bis zur Quadratwurzel zu testen funktioniert, weil n, hätte es einen Teiler größer als seine Wurzel, als Quotienten einen kleineren Teiler hätte, den wir bereits gefunden hätten.
Publicidad
Preguntas frecuentes
- Was ist eine Primzahl?
- Eine Primzahl ist eine ganze Zahl größer als 1, die genau zwei Teiler hat: 1 und sich selbst. Die ersten Primzahlen sind 2, 3, 5, 7, 11, 13 und 17. Die 2 ist die einzige gerade Primzahl, weil jede andere gerade Zahl durch 2 teilbar ist.
- Ist 1 eine Primzahl?
- Nein. Per Definition muss eine Primzahl genau zwei verschiedene Teiler haben, und 1 hat nur einen Teiler (sich selbst). Aus demselben Grund sind 0 und negative Zahlen keine Primzahlen. Die kleinste Primzahl ist die 2.
- Was ist die Primfaktorzerlegung?
- Die Primfaktorzerlegung ist das Schreiben einer Zahl als Produkt von Primzahlen. Zum Beispiel 60 = 2 × 2 × 3 × 5. Der Fundamentalsatz der Arithmetik garantiert, dass jede ganze Zahl größer als 1 genau eine solche Zerlegung besitzt, bis auf die Reihenfolge der Faktoren.
- Wie prüft der Rechner, ob eine Zahl prim ist?
- Er schließt Zahlen unter 2 und gerade Zahlen über 2 aus und versucht dann, durch jede ungerade Zahl bis zur Quadratwurzel der Eingabe zu teilen. Teilt keine davon genau, ist die Zahl prim. Das Anhalten bei der Quadratwurzel macht den Test auch für große Zahlen schnell.
- Warum ist die Primfaktorzerlegung wichtig?
- Die Primfaktorzerlegung ist die Grundlage für das Kürzen von Brüchen, das Finden des größten gemeinsamen Teilers und des kleinsten gemeinsamen Vielfachen sowie für die Public-Key-Kryptographie wie RSA, deren Sicherheit darauf beruht, wie schwer es ist, sehr große Zahlen wieder in ihre Primfaktoren zu zerlegen.