Primzahl-Tester

Primzahl-Check

Mach den Primzahl-Check: Nutze unseren Online-Primzahl-Tester um zu prüfen, ob eine beliebige Zahl eine Primzahl ist oder nicht. Gib einfach eine Zahl ein, und der Online-Rechner führt für Dich eine Primzahlprüfung durch. Das Ergebnis wird Dir in wenigen Millisekunden ermittelt.

Wie kannst Du selbst prüfen, ob eine Zahl eine Primzahl ist? Das erfährst Du auch in diesem Artikel im Abschnitt „Primzahltests“.

Was ist eine Primzahl?

Zur Erinnerung: Eine Primzahl ist in der Mathematik und Zahlentheorie eine Zahl, die nur durch 1 und sich selbst teilbar ist. Beachte allerdings, dass diese Definition nur für die natürlichen Zahlen (also positive ganze Zahlen) gilt. In anderen Zahlenmengen, die auch Nachkkommenstellen erlauben, kann man natürlich jede beliebige Zahl durch beliebig viele andere Zahlen teilen.

Beispiel:

Als Beispiel ist hier eine Liste der ersten 12 Primzahlen: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37.

Warum ist 1 keine Primzahl?

Wie an der oberen Beispielliste erkennbar, ist die kleinste Primzahl die 2. Aber warum ist 1 (Eins) keine Primzahl? Schließlich ist sie nur durch 1 und sich selbst teilbar. Ganz einfach: Per Definition wird erwartet, dass es sich um zwei verschiedene Zahlen handelt: 1 und die Zahl selbst. Es werden also zwei Zahlen (Teiler) erwartet. Die 1 hat jedoch nur einen Teiler und ist somit keine Primzahl. Die kleinste Primzahl ist somit die 2.

Primzahltests

Um zu prüfen ob eine Zahl prim ist, gibt es verschiedene Prüfverfahren.

Probedivision

Ein einfacher Primzahltest ist die Probedivision. Bei der Probedivision prüft man nacheinander, ob die zu untersuchende Zahl n durch Primzahlen teilbar ist. Man beginnt mit der kleinsten Primzahl 2 und teilt solange nacheinander bis eine Primzahl erreicht ist, die kleiner gleich Wurzel(n) ist. Ist die Zahl n durch keine Primzahl teilbar, so ist n selbst eine Primzahl.

Beispiel:

Wir untersuchen ob 97 eine Primzahl ist. Die Wurzel von 97 ist ca. 9,85. Jetzt probieren wir nach einander, ob 97 durch eine Primzahl zwischen 2 und 9 teilbar ist. Als mögliche Primzahlteiler stehen uns: 2, 3, 5 und 7 zur Verfügung. Da 97 durch keine dieser Zahlen teilbar ist, ist der Primzahltest bestanden und 97 ist eine Primzahl.

Der Nachteil dieser Methode ist, dass man alle Primzahlen bis Wurzel(n) kennen muss. Daher eignet sich dieser Primzahltest auch nicht für sehr große Zahlen.

Sieb des Eratosthenes

Das Sieb des Eratosthenes ist ein Algorithmus zur Bestimmung von Primzahlen. Das mathematische Verfahren ist bereits seit der Antike bekannt. So funktioniert das Verfahren:

Alle Zahlen werden bis zu einem frei wählbaren Maximalwert notiert (1, 2, 3, 4, 5, 6…). Die zunächst unmarkierten Zahlen sind potentielle Primzahlkandidaten. Die kleinste unmarkierte Zahl ist immer eine Primzahl. Wenn eine Primzahl gefunden wurde, werden alle Vielfachen dieser Primzahl als zusammengesetzt markiert. Man bestimmt dann im Anschluss die nächstgrößere unmarkierte Zahl. Da sie kein Vielfaches von Zahlen kleiner als sie selbst ist, kann sie nur durch eins und sich selbst teilbar sein. Daher kann es sich nur um eine Primzahl handeln. Man streicht nun wieder alle Vielfachen dieser Zahl und führt das Verfahren anschließend fort, bis man am Listenende angekommen ist.

Weitere Primzahltests

Es gibt noch weitere Primzahltestverfahren, diese sind deutlich moderner, jedoch auch deutlich komplexer. Eine Auswahl der Verfahren soll hier lediglich aufgeführt, nicht aber detailliert erläutert werden.

• Fermatscher Primzahltest
• Solovay-Strassen-Test
• Miller-Rabin-Test
• AKS-Methode

Wir hoffen, dass Dir der Online Primzahl-Tester weitergeholfen hat.