Primzahl prüfen

Hier können Sie kostenlos einen Zahl auf einen Primzahl prüfen.

Zu prüfende Zahl  

   

Stell uns deine Frage. Wir antworten dir schnellstens...

Mit dem Rechner für Primzahlen können Sie ohne viel herum zu probieren herausfinden, ob es sich bei Ihrer Zahl um eine Primzahl handelt.

Was ist eine Primzahl?

Eine Primzahl ist eine natürliche Zahl. Sie hat nur zwei natürliche Zahlen als Teiler.[Sie ist also größer als eins und nur mit sich selbst und 1 ganzzahlig teilbar.

Die kleinsten Primzahlen sind klar definiert und auch leicht zu merken: 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 … Dann jedoch wird es schwieriger und da kommt unser Rechner ins Spiel.

Die Primzahl ist eine natürliche Zahl größer als 1. Von der Zahl eins prim leitet sich der Name ab. Ist eine Zahl keine Primzahl, nennt man sie zusammengesetzt. Ausnahme bilden die Zahlen 0 und 1. Sie sind nicht prim und auch nicht zusammengesetzt.

Die Feststellung der Primzahlen beruht auf drei Sätzen:

1.) Die Existenz und Eindeutigkeit der Primfaktorzerlegung. Jede positive ganze Zahl ist das Produkt von Primzahlen. Die Darstellung der Faktoren ist bis auf ihre Reihenfolge eindeutig. z.B. 6= 3×2 oder 6= 2×3

2.)Den Beweis liefert das Lemma von Euklid:
Ist ein Produkt zweier natürlicher Zahlen durch eine Primzahl teilbar, so ist mindestens einer der Faktoren durch sie teilbar.

3.)Primzahlen lassen sich als Produkt zweier natürlicher Zahlen, die beide größer als 1 sind, darstellen.

Die oben genannten Eigenschaften werden in der Algebra zur Verallgemeinerung des Primzahlbegriffs genutzt.

Schon in der Antike entdeckten die Griechen einige Eigenschaften der Primzahlen und doch sind auch heute noch viele Fragen die Primzahlen betreffend offen. Das ist die Goldbachsche Vermutung, nach der außer 2 jede gerade Zahl in Form einer Summe zweier Primzahlen Darstellzustellen ist, und die Annahme, dass unendlich viele Primzahlzwillinge existieren. Gemeint sind Paare von Primzahlen, deren Differenz gleich 2 ist. 3,5,7…

Lange Zeit blieb das Wissen um die Primzahlen ungenutzt. Mit dem Aufkommen elektronischer Rechenmaschinen spielen die Primzahlen in der Kryptografie eine zentrale Rolle spielen.

Eigenschaften der Primzahlen

Die wichtigsten Eigenschaften der Primzahlen sind:
– außer der Zahl 2 sind alle Primzahlen p ungerade. Alle größeren geraden Zahlen sind durch sich selbst, 1 mindestens 2 teilbar. Damit hat jede Primzahl außer 2 die allgemeine Form 2k+1. k ist eine natürliche Zahl.

– Jede Primzahl p > 3 gehört einer der beiden Klassen „Primzahl der Form 4k+1“ oder „Primzahl der Form 4k+3“ an. Auch hier ist mit k eine natürliche Zahl gemeint. Jede Primzahl p > 3 hat die Form p = 6k+1 oder p = 6k-1. k ist eine natürliche Zahl. Der dirichletsche Primzahlsatz sagt: In jeder dieser vier Klassen gibt es unendlich viele Primzahlen.

– Jede natürliche Zahl mit der Form 4m+3, m ist eine positive ganze Zahl, enthält mindestens einen Primfaktor der die Form 4k+3 hat.

– Eine Primzahl p>2 lässt sich in der Form a²+b² mit ganzen Zahlen a,b schreiben, wenn p die Form 4k+1 hat. Diese Darstellung entspricht der Primfaktorzerlegung

p=(a+b/i)(a-b/i)
im Ring der ganzen gaußschen Zahlen.

Die Zahl ?1 ist der quadratische Rest jeder Primzahl,die die Form 4k+1 hat und der quadratische Nichtrest jeder Primzahl mit der Form 4k+3.

Es gibt eine Reihe von Primzahlentests. Mit unserm Rechner ersparen Sie sich jedoch das Herumrechnen und kommen ganz einfach und innerhalb kürzester Zeit zum Ziel.

Rechner bedienen:

Sie geben Ihre Zahl in das Feld ein, drücken berechnen und bekommen im Antwortfeld angezeigt, ob es eine Primzahl ist oder nicht:

Zu prüfende Zahl 39
Antwort Die Zahl 39 ist keine Primzahl.

Zu prüfende Zahl 43
Antwort Die Zahl ist eine Primzahl.

Häufig gestellte Fragen

Was ist einen Primzahl?

Wie prüft man einen Primzahl?

Häufig gestellte Fragen

Was ist einen Primzahl?

Der Begriff der Primzahlen ist aus dem Lateinischen abgeleitet und geht bis ins Altertum zurück. Wörtlich bedeutet „Primzahl“ (numerus primus) „die erste Zahl“.

Primzahlen sind natürliche Zahlen, das heißt Zahlen ohne Dezimalstellen, die genau durch zwei natürliche Zahlen geteilt werden können, ohne dass dabei ein Divisionsrest entsteht. Diese beiden Teiler sind zum einen die Zahl 1 und zum anderen die Primzahl selbst.

Eine praktische Anwendung von Primzahlen findet man heutzutage hauptsächlich im Bereich der Kryptologie. Verschlüsselungsalgorithmen gelten als umso sicherer, je stärker sie auf Primzahlen aufbauen. Dies hat seine Begründung darin, dass für Nicht-Primzahlen schneller ein alternativer Schlüssel errechnet oder auch durch Ausprobieren gefunden werden kann, da sie sich auf Produkte anderer (kleinerer) Zahlen zurückführen lassen.

Die Menge der Primzahlen gilt grundsätzlich als nicht begrenzt. Diese auch als „Satz des Euklid“ benannte Aussage wird verständlich, wenn man die Menge aller natürlichen Zahlen als unbegrenzt annimmt.  Es werden bis heute immer noch Preisgelder und Auszeichnungen für die Entdeckung neuer Primzahlen vergeben.

Wie prüft man einen Primzahl?

Eine gängige Methodik zur Überprüfung, ob eine Zahl eine Primzahl ist, kombiniert einfache mathematische Grundregeln mit „Ausprobieren“. Dazu wird die zu prüfende Zahl zunächst auf folgende Teilbarkeiten hin untersucht:

Zahl ist eine gerade Zahl                          → durch 2 teilbar    → keine Primzahl
Quersumme der Zahl durch 3 teilbar        → durch 3 teilbar    → keine Primzahl
Zahl endet auf 5                                       → durch 5  teilbar    → keine Primzahl
Zahl endet auf 0                                       → durch 10 teilbar    → keine Primzahl

Haben diese einfachen Prüfungen noch kein Ausschlusskriterium für eine Primzahl bestätigt, dann wird der Prüfling schrittweise (nacheinander) durch alle bekannten Primzahlen zwischen 2 und der Wurzel aus der zu prüfenden Zahl geteilt. Alle Nicht-Primzahlen scheiden als Divisoren von Haus aus aus, da eine Primzahl nur ein Produkt ihrer selbst mit der Zahl 1 sein darf und Nicht-Primzahlen andere mögliche Teiler bereits beinhalten.

Nur wenn die Division durch all diese Primzahlen (die kleiner sind als der Prüfling) fehlschlägt, also kein einziges Mal ein ganzzahliges Ergebnis liefert, dann ist der Prüfling selbst auch eine Primzahl.

Diese Verfahren wird auch als „Probeverfahren“ bezeichnet. Es ist allerdings sehr aufwendig, wenn der Prüfling sehr groß ist.

Es gibt eine Vielzahl weiterer Verfahren, die teils auf sehr komplexen mathematischen Grundlagen aufsetzen, genannt seien exemplarisch an dieser Stelle der fermatische Primzahltest, der Miller-Rabin-Test oder auch der Satz von Euler.