Primzahl-Rechner
Ist die Zahl prim? Nächste Primzahl finden und Primfaktorzerlegung berechnen
- Aktualisiert
Ganze Zahl bis 10.000.000
Ist 17 eine Primzahl?
Ja
Ja, 17 ist eine Primzahl. 17 ist nur durch 1 und durch sich selbst teilbar.
So wurde geprüft
Es genügt, Teiler bis zur Wurzel zu prüfen: √17 ≈ 4,12. Keine Zahl von 2 bis 4 teilt 17 ohne Rest – also ist 17 eine Primzahl.
- Nächste Primzahl
- 19
- Primfaktoren
- 17
RZ-26 · headon.pro
Primzahlen – Grundlagen und Bedeutung
Die Atome der natürlichen Zahlen und ihre Anwendungen
Primzahlen sind natürliche Zahlen größer als 1, die nur durch 1 und sich selbst teilbar sind. Sie gelten als die „Atome" der Arithmetik: Der Fundamentalsatz der Arithmetik besagt, dass jede natürliche Zahl größer als 1 eindeutig als Produkt von Primzahlen darstellbar ist. Diese Eigenschaft macht Primzahlen zur Grundlage der modernen Zahlentheorie und Kryptographie.
Der effizienteste Primzahltest für mittelgroße Zahlen ist der Trial-Division-Algorithmus: Man prüft alle Teiler von 2 bis zur Quadratwurzel der zu prüfenden Zahl. Ist keiner ein Teiler, ist die Zahl prim. Für n = 17: √17 ≈ 4,1, also teste 2, 3, 4 – keiner teilt 17 → 17 ist prim. Für große Zahlen (über 10⁷) werden probabilistische Tests wie Miller-Rabin verwendet, die deutlich schneller sind.
Die Primfaktorzerlegung schreibt jede zusammengesetzte Zahl als Produkt ihrer Primfaktoren. Für 12: 12 = 2 × 2 × 3. Diese Zerlegung ist die Basis für die Berechnung von GGT und KGV. Der RSA-Verschlüsselungsalgorithmus, der das Internet sichert, basiert auf der Tatsache, dass die Primfaktorzerlegung großer Zahlen (hunderte Stellen) praktisch unmöglich ist – selbst für moderne Supercomputer.
Bekannte Primzahlreihen: Die Menge der Primzahlen unter 100 umfasst 25 Zahlen: 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. Die Mersenne-Primzahlen (Zahlen der Form 2ⁿ − 1, z. B. 31 = 2⁵ − 1) sind für die Suche nach besonders großen Primzahlen relevant. Die aktuell größte bekannte Primzahl hat über 40 Millionen Dezimalstellen und ist eine Mersenne-Primzahl.
Rechenbeispiele
- Zu prüfen
- 17
- √17 ≈ 4,1 → teste 2, 3, 4
- kein Teiler
- Ergebnis
- 17 ist prim
- 18 ÷ 2 = 9
- Faktor: 2
- 9 ÷ 3 = 3
- Faktor: 3
- 3 ÷ 3 = 1
- Faktor: 3
- 18 = 2 × 3 × 3
- 2 × 3²
Häufige Fragen zum Primzahl-Rechner
Primzahlen, Primfaktorzerlegung und mathematische Hintergründe
Was ist eine Primzahl?
Eine Primzahl ist eine natürliche Zahl größer als 1, die nur durch 1 und sich selbst teilbar ist. Die kleinsten Primzahlen sind: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, … Die Zahl 2 ist die einzige gerade Primzahl. Alle geraden Zahlen ab 4 sind keine Primzahlen, da sie durch 2 teilbar sind. Primzahlen sind die „Atome" der natürlichen Zahlen: Jede Zahl lässt sich als Produkt von Primzahlen darstellen.
Wie prüft man, ob eine Zahl eine Primzahl ist?
Um zu prüfen, ob n eine Primzahl ist, testet man alle Teiler von 2 bis √n. Wenn keiner dieser Teiler n ohne Rest teilt, ist n eine Primzahl. Die Grenze √n reicht, weil ein Teiler größer als √n immer einen entsprechenden Teiler kleiner als √n hätte. Für n=17: √17 ≈ 4,1. Teste 2, 3, 4: Keiner teilt 17 ohne Rest → 17 ist prim.
Was ist die Primfaktorzerlegung?
Die Primfaktorzerlegung (oder Primzerlegung) einer Zahl n schreibt n als Produkt von Primzahlen. Nach dem Fundamentalsatz der Arithmetik gibt es für jede natürliche Zahl > 1 genau eine solche Zerlegung (bis auf Reihenfolge). Beispiel: 12 = 2 × 2 × 3 = 2² × 3. Die Primfaktorzerlegung ist die Basis von GGT und KGV sowie von modernen Verschlüsselungsverfahren wie RSA.
Gibt es unendlich viele Primzahlen?
Ja! Euklid bewies bereits um 300 v. Chr., dass es unendlich viele Primzahlen gibt: Angenommen, es gäbe nur endlich viele p₁, p₂, …, pₙ. Dann wäre N = p₁ × p₂ × … × pₙ + 1 durch keine der bekannten Primzahlen teilbar. N selbst müsste also entweder prim sein oder einen neuen Primfaktor haben – Widerspruch. Daher gibt es immer weitere, noch unbekannte Primzahlen.
Was ist die Goldbach-Vermutung?
Die Goldbach-Vermutung (1742) besagt, dass jede gerade Zahl > 2 als Summe zweier Primzahlen darstellbar ist. Zum Beispiel: 4 = 2+2, 6 = 3+3, 8 = 3+5, 100 = 3+97. Sie gilt für alle geprüften Zahlen bis in den Billionenbereich, ist aber bis heute nicht bewiesen und eines der berühmtesten ungelösten Probleme der Mathematik. Primzahlen halten also noch viele Geheimnisse bereit.