Primzahlen – Erklärung, Berechnungen und Beispiele

Was ist eine Primzahl?

Eine Primzahl ist eine natürliche Zahl, die ganzzahlig ohne Rest nur durch sich selbst und 1 teilbar ist. Im Umkehrschluß bedeutet dies, daß sich die Menge der Primzahlen dadurch auszeichnet, daß sie die einzigen natürlichen Zahlen sind, die exakt zwei Teiler besitzen. Die 1 ist zwar auch durch sich selbst und 1 teilbar, gilt aber nicht als Primzahl.

Dadurch kann jede natürliche Zahl, die größer als 1 ist, eindeutig als Produkt von Primzahlen dargestellt werden (bis auf die Reihenfolge).

Gibt es unendlich viele Primzahlen?

Ja, es gibt unendlich viele Primzahlen. Der Beweis ist ziemlich einfach:
Man bildet aus allen bisher gefundenen Primzahlen p1, …, pn das Produkt: p1*…*pn und addiert 1. Diese Zahl ist nun nicht durch eine der Zahlen p1 bis pn ohne Rest teilbar. Also ist diese Zahl wieder einen neue Primzahl. Auf diese Weise lassen sich unendlich viele Primzahlen bilden.

Primzahltests

Das erste Verfahren zum Finden von Primzahlen ist als das Sieb des Eratosthenes bekannt. Dabei werden alle natürlichen Zahlen bis zu einer Grenze notiert. Dann werden erst alle Vielfachen von 2 herausgestrichen. Anschließend werden die Vielfachen von der nächsten stehengebliebenen Zahl (also der 3) gestrichen und anschließend die Vielfachen der nächsten stehen gebliebenen Zahl (der 5). So werden alle Primzahlen bis zu der gewünschten Grenze gefunden.

Allerdings muß man nicht alle Zahlen prüfen. Beim Test, ob einen natürliche Zahl n eine Primzahl ist, reicht es, mögliche Teiler nur bis zur Wurzel aus n zu testen.