Wie prüft man, ob eine Zahl eine Primzahl ist?
Eine Primzahl hat genau zwei Teiler: 1 und sich selbst (2, 3, 5, 7, 11, 13 …). Der Rechner prüft Teiler bis zur Wurzel der Zahl — teilt keiner sie ohne Rest, ist sie prim. Er funktioniert für Zahlen bis zu einer Billion (10¹²).
Eine zusammengesetzte Zahl lässt sich auf genau eine Weise in Primfaktoren zerlegen. Beispiel: 360 = 2³ × 3² × 5. Sie hat 24 Teiler, die vorige Primzahl ist 359, die nächste 367.
Wie zählt man die Teiler?
Aus der Primfaktorzerlegung: zu jedem Exponenten 1 addieren und multiplizieren. Für 360 = 2³ × 3² × 5¹ sind das (3 + 1)(2 + 1)(1 + 1) = 24 Teiler.
Wissenswertes
- 2 ist die einzige gerade Primzahl.
- 1 ist keine Primzahl — sie hat nur einen Teiler.
- Es gibt unendlich viele Primzahlen — Euklid bewies das um 300 v. Chr.
- Große Primzahlen sind die Grundlage der RSA-Verschlüsselung, die unter anderem HTTPS-Verbindungen schützt.
Häufige Fragen
Ist 97 eine Primzahl?
Ja — sie ist nicht durch 2, 3, 5 oder 7 teilbar, und 11² = 121 ist schon größer als 97.
Wie viele Primzahlen gibt es bis 100?
25: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.