Primzahlen

Eine Primzahl ist eine Zahl, die als Teiler nur - trivialerweise - die 1 und sich selber hat, also durch keine andere Zahl ohne Rest oder Nachkommastellen teilbar ist.
Dies ist eine einfache Definition oder Regel. Es gibt (wahrscheinlich) keine andere. Ein Schüler fragte mich einmal, nachdem ich ihn bat die ersten Primzahlen aufzuschreiben und dann ein Computerprogramm dafür zu entwerfen, da müsse er aber erst die Regel wissen!
Das Auftreten der Primzahlen innerhalb der natürlichen Zahlen erscheint regellos.

Es gibt unendlich viele Primzahlen.
Es gibt wahrscheinlich unendlich viele sog. Primzahlzwillinge wie 5 und 7.
Es gibt wahrscheinlich auch unendlich viele Primzahlvierlinge wie 5,7,11,13.
Es gibt aber auch beliebig große primzahlfreie Bereiche zwischen zwei Primzahlen.

Wir erzeugen beliebig viele Primzahlen indem wir jede ungerade Zahl z testen, ob sie durch alle Primzahlen p <= Wurzel(z) teilbar ist.
Größere Testzahlen als √z brauchen wir nicht zu testen, da dann ja der andere Teiler kleiner sein müsste und also schon getestet worden ist. Etwas verschwenderisch aber einfacher ist es , den Teilungsversuch mit allen ungeraden Zahlen statt mit allen Primzahlen ≤ √z durchzuführen.

Berechnen Sie die ersten n Primzahlen

Berechnung von Primzahlen in bestimmten Grenzen

Was die chemischen Elemente für die Materie sind, die uns umgibt, sind die Primzahlen für alle natürlichen Zahlen. Wie jeder Apfel aus Kohlenstoff, Wasserstoff, Sauerstoff und anderen der etwa 100 chemischen Elemente aufgebaut ist, so ist jede Zahl ein Produkt aus Primzahlen.
Eine Zahl kann als Produkt irgendwelcher Teiler dargestellt werden, z.B. 20 = 5 * 4, und diese sind entweder selbst prim, oder sie lassen sich weiter teilen bis man bei Primzahlen landet: 20 = 5 * 2 * 2.
Diese Faktorenzerlegung ist (natürlich bis auf die Reihenfolge) für jede Zahl eindeutig, z = ∏ p_j^k_j = p₁^k₁ · p₂^k₂ ··· p_n^k_n.
Dass es unendlich viele Primzahlen geben muss, hat schon Euklid bewiesen. Nimmt man an, die Menge der Primzahlen P = {2,3,5,...,p} sei endlich und p sei die letzte Primzahl. Dann ist q = 2·3·5···p + 1 eine Zahl die durch keine von "allen" Primzahlen aus P teilbar ist, also entweder selbst prim ist oder Primzahlen als Teiler enthält, die nicht in P enthalten sind , was ein Widerspruch zur Vorraussetzung ist.