Primzahlen: Meta: Überblick

Primzahlen: Meta

Primzahlen

Einleitung

Dass eine Primzahl eine natürliche Zahl größer eins ist, die nur durch eins und sich selbst teilbar ist, kann man als Eigenschaft der Primzahl bezeichnen. Es ist die Eigenschaft, über die sich die Primzahl definiert. Daneben hat die Primzahl noch eine Menge anderer Eigenschaften. Einige dieser Eigenschaften sind trivial, haben aber Auswirkungen auf Zahlen, die aus diesen Primzahlen zusammengesetzt sind. Andere Eigenschaften treffen auch auf Zahlen zu, die keine Primzahlen sind, und die deswegen nur bedingt als Primzahlkriterium eingesetzt werden können.

Primzahlen der Form 4n+1 und 4n-1

Außer 2 ist jede Primzahl ungerade und hat deshalb die Form $4n+1$ oder $4n-1$. Auf äquivalente Weise könnte man sagen eine ungerade Zahl hat die Form $4n+1$ oder $4n+3$, denn $4n+3=4(n+1)-1=4n'-1$. Die beiden möglichen Formen spielen eine unterschiedliche Rolle bei ungeraden, zusammengesetzten natürlichen Zahlen.

Wenn eine solche Zahl die Form $4n-1\$ besitzt, muss sie eine ungerade Anzahl an Primfaktoren der Form $4p-1\$ besitzen, also mindestens einen Primfaktor dieser Form.

Eine ungerade natürliche Zahl der Form $4n+1\$ wiederum hat entweder keine Primfaktoren der Form $4p-1\$ oder ihre Anzahl ist gerade.

Das lässt sich über folgende Sätze zeigen:

Das Produkt zweier Zahlen der Form $4n-1$ hat die Form $4n+1$

$(4n-1)(4m-1)=16nm-4(n+m)+1=4(4nm-n-m)+1=4k+1$

Das Produkt zweier Zahlen der Form $4n+1$ hat die Form $4n+1$

$(4n+1)(4m+1)=16nm+4(n+m)+1=4(4nm+n+m)+1=4k'+1$

Das Produkt einer Zahl der Form $4n-1$ und einer Zahl der Form $4n+1$ hat die Form $4n-1$

$(4n-1)(4m+1)=16nm+4(n-m)-1=4(4nm+n-m)-1=4k''-1$

Primzahlen der Form 6n+1 und 6n-1

Primzahlen, die größer als drei sind, haben entweder die Form $6n+1$ oder $6n-1$. Statt der Form $6n-1$ kann man auch sagen die Zahl sei der Form $6n'+5$, denn $6n-1=6(n-1)+5=6n'+5.$

Zahlen der Form $6n+2$ und $6n+4$ sind gerade, also keine Primzahlen. Eine Zahl der Form $6n+3$ ist durch 3 teilbar und deshalb ebenso keine Primzahl. So trivial das Ganze ist, hat es doch eine Auswirkung, zum Beispiel auf Carmichael-Zahlen einer bestimmten Form.

Eine Zahl $c=p_{1}\cdot p_{2}\cdot p_{3}$ mit drei Primfaktoren

$p_{1}=p,p_{2}=2p-1$ und $p_{3}=3p-2$

ist eine bestimmte Form der Carmichael-Zahl. Dabei kann die Primzahl $p$ nur der Form $p=6n+1$ sein, denn für $p=6n-1$ gilt

$p_{2}=2p-1=12n-3,$

eine Zahl teilbar durch 3, und deshalb keine Primzahl. Es gilt also:

$p_{1}=p=6n+1,p_{2}=2p-1=12n+1$ und $p_{3}=3p-2=18n+1,$

und damit ist die Aussage äquivalent mit dem Satz:

Eine Zahl mit den drei Primfaktoren $6n+1,12n+1$ und $18n+1$ ist eine Carmichael-Zahl.

Binomialkoeffizient

Für eine Primzahl $p\$ gilt: $p\$ teilt $p \choose m$ für alle $m\$ mit $1\leq m\leq p-1$. Warum das so ist und warum die Umkehrung (Wenn für eine natürliche Zahl $n\$ gilt, dass $n\$ teilt $n \choose m$ für alle $m\$ mit $1\leq m\leq n-1$, dann ist $n\$ eine Primzahl) gilt, lässt sich an der folgenden Überlegung verdeutlichen:

Angenommen man hat eine zusammengesetzte Zahl $n=p_{1}\cdot p_{2}\cdot ...\cdot p_{n}$. Als Beispiel nehmen wir die Zahl $91=7\cdot 13$. Mit der $91\$ betrachten wir zwei Fälle, nämlich $91 \choose 7$ und $91 \choose 13$. Im ersten Fall ist ${91 \choose 7}={\frac {91\cdot 90\cdot 89\cdot 88\cdot 87\cdot 86\cdot 85}{1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6\cdot 7}}$. Wenn wir den Bruch auskürzen wollen, werden wir feststellen, dass von den Zahlen über dem Bruchstrich nur eine einzige Zahl durch $7\$ teilbar ist, nämlich die $91\$ selbst. Daraus folgt, dass die Zahl, die den Bruch ${\frac {91\cdot 90\cdot 89\cdot 88\cdot 87\cdot 86\cdot 85}{1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6\cdot 7}}$ repräsentiert, gar nicht durch $91\$ teilbar sein kann. Das gleiche gilt für ${91 \choose 13}={\frac {91\cdot 90\cdot 89\cdot 88\cdot 87\cdot 86\cdot 85\cdot 84\cdot 83\cdot 82\cdot 81\cdot 80\cdot 79}{1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6\cdot 7\cdot 8\cdot 9\cdot 10\cdot 11\cdot 12\cdot 13}}$. Auch hier ist die einzige Zahl über dem Bruchstrich, die durch $13\$ teilbar ist, die $91\$ selbst. Warum ist das so? Weil in einem Produkt aus $n\$ aufeinander folgenden Zahlen genau eine Zahl durch $n\$ teilbar sein muss. Bei einer Primzahl trifft dieser Fall genau für $p \choose p$ zu. Aber dieser Binomialkoeffizient spielt für die Eigenschaft von Primzahlen bezüglich der Binomialkoeffizienten gar keine Rolle.

Der kleine Fermat

Die folgenden Eigenschaften haben mit dem kleinen fermatschen Satz zu tun und haben zu Primzahltests auf Basis von Wahrscheinlichkeiten geführt. Natürliche Zahlen, die keine Primzahlen sind und diese Tests trotzdem bestehen, also aufgrund dieser Tests fälschlicherweise als Primzahlen angesehen werden könnten, sind fermatsche Pseudoprimzahlen.

Der kleine Fermatsche Satz

Angeblich war chinesischen Mathematikern schon ca. 500 v. Chr. bekannt, dass für jede Primzahl $p$ gilt, dass $p$ die Zahl $2^{p}-2$ teilt. Sie vermuteten allerdings fälschlicherweise, dass auch die Umkehrung stimmt; dass also, wenn $n$ die Zahl $2^{n}-2$ teilt, dieses $n$ eine Primzahl sein muss.

Die Verallgemeinerung

Wenn $p$ eine Primzahl ist, dann gilt, dass $p$ jedes $a^{p}-a$ teilt.

ist nach dem Juristen und Amateur-Mathematiker Pierre de Fermat als kleiner fermatscher Satz bekannt geworden. Benutzt wird aber eher folgende Variante:

Wenn $p$ eine Primzahl ist, dann gilt $a^{p-1}\equiv 1{\pmod {p}}$ für jedes zu $p$ teilerfremde $a>1$.

Der Satz lässt sich einschränken auf: Wenn $p$ eine Primzahl ist, dann gilt für alle $2\leq a\leq p-2$ dass $a^{p-1}\equiv 1{\pmod {p}}$ ist.

Umgekehrt gilt nicht dass eine Zahl $n$, wofür $a^{n-1}\equiv 1{\pmod {n}}$ für jedes zu $n$ teilerfremde $a>1\$,unbedingt eine Primzahl ist. Ist $n$ keine Primzahl, dann nennt man sie Carmichael-Zahl.

Euler

Eine etwas stärke Eigenschaft, die sich auf den kleinen fermatschen Satz zurückführen lässt, ist folgende:

Wenn $p$ eine Primzahl ist, so gilt für jede zu $p$ teilerfremde natürliche Zahl $a$

$(a^{\frac {p-1}{2}}-1)\cdot (a^{\frac {p-1}{2}}+1)=a^{p-1}-1\equiv 0{\pmod {p}}.$

Es gilt folglich entweder

$a^{\frac {p-1}{2}}\equiv 1{\pmod {p}},$

oder

$a^{\frac {p-1}{2}}\equiv -1{\pmod {p}}.$

Diese Folgerung wird Leonhard Euler zugeschrieben.

Es lässt sich beweisen dass im ersten Fall die Zahl $a$ modulo $p$ ein quadratischer Rest ist, und im zweiten Fall ein quadratischer Nichtrest. Es gilt also die Kongruenz:

$a^{\frac {p-1}{2}}\equiv \left({\frac {a}{p}}\right){\pmod {p}}$.

Dabei ist

$\left({\frac {a}{p}}\right)={\begin{cases}1&{\mbox{wenn }}a{\mbox{ quadratischer Rest modulo }}p{\mbox{ ist}}\\-1&{\mbox{wenn }}a{\mbox{ quadratischer Nichtrest modulo }}p{\mbox{ ist}}\\0&{\mbox{wenn }}a{\mbox{ ein Vielfaches von }}p{\mbox{ ist}}\end{cases}}$

das Legendre-Symbol, ein Spezialfall des Jacobi-Symbols, das die gleiche Schreibweise hat, und für Primzahlen p übereinstimmen.

Der Beweis stützt auf der Ergebnisse:

• Es gibt modulo p genau (p-1)/2 Quadratreste.
• Die Gleichung $a^{\frac {p-1}{2}}-1\equiv 0{\pmod {p}}$ hat nicht mehr als (p-1)/2 Lösungen.

Wenn a ein Quadratrest modulo p ist, gilt $a\equiv x^{2}{\pmod {p}}$, also

$a^{\frac {p-1}{2}}\equiv x^{p-1}\equiv 1{\pmod {p}}.$

Es sind also genau die (p-1)/2 Quadratreste wofür gilt $a^{\frac {p-1}{2}}\equiv 1{\pmod {p}}.$ Fuer die restliche Zahlen a, die quadratische Nichtreste, gilt:

$a^{\frac {p-1}{2}}\equiv -1{\pmod {p}}.$

Ein Beispiel: 7 ist die Primzahl $p\$, 2 ist die Basis $a_{1}\$ und 5 die Basis $a_{2}\$.

Es gilt: $2^{\frac {7-1}{2}}\equiv 1\mod 7$, da Quadratzahlen der Form $7n+2$ existieren. Es gilt: $5^{\frac {7-1}{2}}\equiv -1\mod 7$, da keine Quadratzahlen der Form $7n+5$ existieren.

Dass aus $a^{\frac {p-1}{2}}\equiv 1\mod p$ bzw. $a^{\frac {p-1}{2}}\equiv -1\mod p$ folgt, dass $a^{p-1}\equiv 1\mod p$ gilt, läßt sich daraus ersehen, dass

$\left(a^{\frac {p-1}{2}}\right)^{2}=a^{2\cdot {\frac {p-1}{2}}}=a^{p-1}$ und $1\cdot 1=(-1)\cdot (-1)=1$ ist.

Lucas-Theorem

Für positive natuerliche Zahlen m und n und die Primzahl p gilt:

${\binom {m}{n}}\equiv \prod _{i=0}^{k}{\binom {m_{i}}{n_{i}}}{\pmod {p}}.$

Darin sind:

$m=m_{k}p^{k}+m_{k-1}p^{k-1}+\cdots +m_{1}p+m_{0},$

und

$n=n_{k}p^{k}+n_{k-1}p^{k-1}+\cdots +n_{1}p+n_{0}$

die Entwicklungen von m und n mit Beziehung zur Basis p.

Wilson

Der Satz von Wilson besagt, dass eine natürliche Zahl n > 1 dann und nur dann eine Primzahl ist, wenn

$(n-1)!\ \equiv -1{\pmod {n}}.$

Daraus folgt

$(n-2)!\ \equiv 1{\pmod {n}}.$

Lineare Rekursionen

Perrin-Folge

Die Perrin-Folge (benannt nach dem Mathematiker R.Perrin) ist wie folgt definiert:

$P_{0}=3$

$P_{1}=0$

$P_{2}=2$

$P_{n}=P_{n-2}+P_{n-3}$

Für die Perrin-Folge gilt nun, wenn $p$ eine Primzahl ist, dass $P_{p}$ durch p teilbar ist.

Die Lucas-Folge V_n (P,Q)

Die allgemeinen Lucas-Folgen $U_{n}(P,Q)$ und $V_{n}(P,Q)$ sind nach dem französischen Mathematiker Édouard Lucas benannt, der sich als erster mit ihnen beschäftigt hat.

Die allgemeine Lucas-Folge $V_{n}(P,Q)$ ist definiert als diejenigen Folge, wofür

$V_{0}(P,Q)=2,\quad V_{1}(P,Q)=P$

und die für n > 1 den Rekursionsformel

$V_{n}(P,Q)=P\cdot V_{n-1}(P,Q)-Q\cdot V_{n-2}(P,Q)$

genügt.

Für die Lucasfolge $V_{n}(P,Q)$ gilt, wenn $p$ eine Primzahl ist, dass $V_{p}(P,Q)-P$ durch p teilbar ist.

Die Lucas-Folge U_n (P,Q)

Die allgemeine Lucas-Folge $U_{n}(P,Q)$ ist definiert als diejenige Folge, wofür

$U_{0}(P,Q)=0,\quad U_{1}(P,Q)=1$

und die für n > 1 den Rekursionsformel

$U_{n}(P,Q)=P\cdot U_{n-1}(P,Q)-Q\cdot U_{n-2}(P,Q)$

genügt.

Primzahlen

Wie im Vorwort schon erwähnt, lässt sich eine Primzahl als eine natürliche Zahl größer 1, die nur durch 1 und sich selbst teilbar ist, definieren. Aufgrund dieser Eigenschaft existiert der naive Primzahlentest, bei der eine Zahl $n$ auf die Teilbarkeit durch alle Zahlen zwischen 2 und ${\sqrt {n}}$ getestet wird:

Eine Primzahl: 7 $7\mod 2=1$ : teilerfremd! $7\mod 3=1$ : teilerfremd! $7\mod 4=3$ : teilerfremd! $7\mod 5=2$ : teilerfremd! $7\mod 6=1$ : teilerfremd!

Keine Primzahl: 12 $12\mod 2=0$ : nicht teilerfremd! $12\mod 3=0$ : nicht teilerfremd! $12\mod 4=0$ : nicht teilerfremd! $12\mod 5=2$ : teilerfremd! $12\mod 6=0$ : nicht teilerfremd!

In Zusammenhang mit der oben angegebenen Eigenschaft "Eine Primzahl als eine natürliche Zahl größer 1, die nur durch 1 und sich selbst teilbar ist" gibt es noch weitere Eigenschaften, die sich aus dieser Eigenschaft ableiten lassen:

1. Zwei natürliche Zahlen, deren Summe eine Primzahl ergeben, sind immer teilerfremd. Allerdings ergibt die Summe zweier teilerfremder natürlicher Zahlen nicht immer eine Primzahl.

Eine Primzahl: 11 $11=2+9$ : teilerfremd! $11=3+8$ : teilerfremd! $11=4+7$ : teilerfremd! $11=5+6$ : teilerfremd!

Keine Primzahl: 15 $15=2+13$ : teilerfremd! $15=3+12$ : nicht teilerfremd! $15=4+11$ : teilerfremd! $15=5+10$ : nicht teilerfremd! $15=6+9$ : nicht teilerfremd! $15=7+8$ : teilerfremd!

2. Es ist nicht möglich, eine Primzahl in die Form eines Rechtecks zu bringen.
Beispiele:

--1--2---3----4---5----6----7----8----9----10-----11----11---
--X--XX--XXX--XX--XXX--XXX-XXXX-XXXX--XXX--XXXXX--XXXX--XXXXX
--------------XX--XX---XXX-XXX--XXXX--XXX--XXXXX--XXXX--XXXXX
--------------------------------------XXX---------XXX---X----

Primzahlen

In Kapitel I. Eigenschaften wurde der kleine fermatsche Satz $a^{n}-a\equiv 0{\pmod {n}}\$ aufgeführt, dass also $a^{n}-a\$ durch $n\$ teilbar ist, wenn $n\$ eine Primzahl ist. Man kann $a^{p}-a\$, mit ihrer Eigenschaft, durch die Primzahl $p\$ teilbar zu sein, immer wieder mal antreffen. Im weiteren wird $a^{p}-a\$ als $a^{p}-a^{1}\$ dargestellt.

Der kleine Fermat und die allgemeinen Lucas-Folge V(P,Q) = aⁿ + bⁿ

Für alle Lucas-Folgen $V_{n}(P,Q)=a^{n}+b^{n}\$ mit $P>0\$ und $Q=\pm 1$ gilt, dass $(V_{n}(P,Q)-P)\$ durch $n\$ teilbar ist, wenn $n\$ eine Primzahl ist. Oder anders ausgedrückt:

$V_{n}(P,Q)\equiv P{\pmod {n}}$ für alle $n$, die Primzahlen sind.

Es trifft nun zu, dass $V_{1}(P,Q)\$ immer $P\$ ist. Demzufolge lässt sich auch schreiben: Wenn $n\$ eine Primzahl ist, dann gilt, dass $V_{n}(P,Q)-V_{1}(P,Q)\$ durch $n\$ teilbar ist. Das sieht dem kleinen fermatschen Satz ziemlich ähnlich. Und in der Tat ist der Spezialfall: $V_{n}(A+1,A)-V_{1}(A+1,A)\$ mit $A\geq 1$ identisch mit dem kleinen fermatschen Satz $a^{n}-a^{1}\$.

Primzahlen

Einleitung

Wir können davon ausgehen, dass Primzahlen existieren, denn sonst würde es dieses Kapitel und das ganze Buch nicht geben. Obwohl ein paar kritische Leser einwerfen, dass dies gar nicht so sicher ist. Wie dem auch sei, wir gehen davon aus, dass es Primzahlen gibt. Um die große Frage, ob es nur endlich viele Primzahlen oder doch unendlich viele Primzahlen gibt, beziehungsweise die Beantwortung dieser Frage geht es in diesem Kapitel. Es gibt also unendlich viele Primzahlen, und die folgenden Beweise handeln davon.

Euklids Beweis

Der um 300 v. Chr. in Alexandria lebende Mathematiker Euklid hat folgenden Beweis geliefert: Angenommen, es gäbe endlich viele Primzahlen. Dann gäbe es die größte Primzahl $p_{n}$. Man kann nun das Produkt aller Primzahlen $p_{n}\#=p_{1}\cdot p_{2}\cdot p_{3}\cdot \dots \cdot p_{n}$ bilden. $p_{n}\#$ ist durch alle Primzahlen von $p_{1}$ bis $p_{n}$ teilbar. Die Zahl $p_{n}\#+1$ ist wiederum durch keine der Primzahlen zwischen $p_{1}$ und $p_{n}$ teilbar. Daraus folgt, dass $p_{n}\#+1$ entweder eine weitere Primzahl ist, oder das Produkt von noch unbekannten Primzahlen ist. Egal was nun zutreffen mag, es gibt immer mehr Primzahlen als die Primzahlen, die schon bekannt sind.

Beispiele

Angenommen, 11 sei die größte Primzahl, dann ist aber:

$2\cdot 3\cdot 5\cdot 7\cdot 11+1=2311$

eine Primzahl größer als 11.

Angenommen, 13 sei die größte Primzahl, dann ist aber:

$2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13+1=30031$.

zwar selbst keine Primzahl, jedoch das Produkt der Primzahlen 59 und 509, beide größer als 13.

Stieltjes Beweis (1890)

Angenommen $p_{1},\ p_{2},\ p_{3},\ldots ,\ p_{r}$ seien die einzigen Primzahlen, die existieren. Dann gilt für die Zahl $N=p_{1}\cdot p_{2}\cdot p_{3}\cdot \ldots \cdot p_{r}$, dass sie sich in der Form $N=m\cdot n$ zerlegen lässt, wobei für beide Zahlen $m$ und $n$ angenommen werden kann, dass sie größer 1 sind und dass jede Primzahl $p_{i}$ entweder $m$ oder $n$ teilt, aber nicht beide zugleich. Aus diesem Grund ist $m+n$ durch keine der existierenden Primzahlen teilbar. Da aber $m+n>1$ ist, ist $m+n$ eine weitere, größere Primzahl oder durch eine weitere noch unbekannte Primzahl teilbar.

Stieltjes Beweis ist im Grunde eine Verallgemeinerung von Euklids Satz, da dieser mit $n=1$ einen Spezialfall von Stieltjes Beweis darstellt.

Beispiel

Angenommen es gäbe nur die 4 Primzahlen 2, 3, 5 und 7. Dann wäre N = 2 · 3 · 5 · 7 = 210. N ließe sich beispielsweise in die Faktoren 15 (= 3 · 5) und 14 (= 2 · 7) zerlegen. 15 + 14 = 29. Die Zahl 29 lässt sich weder durch 2, 3, 5 oder 7 teilen. Also ist 29 eine Primzahl oder durch wenigstens zwei, zueinander teilerfremde, Primzahlen teilbar, die sich nicht in der Menge {2, 3, 5, 7} befinden.

Schorns Beweis

Vorbemerkung zu "paarweise teilerfremd"

Dieser (Schorns) und der folgende (Goldbachs) Beweis erfordern eine Erklärung. Zwei Zahlen a₁ und a₂ (nicht unbedingt Primzahlen) ohne gemeinsame Primfaktoren, also mit ggT (größter gemeinsame Teiler) 1, heißen teilerfremd. Eine Menge von Zahlen heißt paarweise teilerfremd, wenn je zwei beliebige Zahlen aus dieser Menge teilerfremd sind.

Beweis

Angenommen, es gäbe genau $m$ verschiedene Primzahlen. Dann setze $\!n=m+1$. Die $n$ natürlichen Zahlen $n!\cdot i+1$ für $i=1,\dots ,n$ sind paarweise teilerfremd. Wenn eine Primzahl $p_{i}$ die natürliche Zahl $n!\cdot i+1$ teilt, dann sind die Primzahlen $p_{1},p_{2},...,p_{n}\ \ \ n=m+1$ unterschiedliche Primzahlen, was im Widerspruch zu unserer anfänglichen Annahme steht, dass es genau $m$ verschiedene Primzahlen gibt.

Beispiel

Angenommen, man geht davon aus, dass es genau 3 Primzahlen gibt. Dann ist $n=3+1=4$. Mit dieser Zahl kann man die folgenden 4 Zahlen konstruieren:

$4!\cdot 1+1=25=5^{2},\ \ 4!\cdot 2+1=49=7^{2},\ \ 4!\cdot 3+1=73,\ \ 4!\cdot 4+1=97$.

Alle vier Zahlen sind also paarweise teilerfremd. Das bedeutet auch, dass es mindestens 4 verschiedene Primzahlen gibt, was der Annahme widerspricht, dass es nur genau 3 Primzahlen gibt.

Vorteil

Der große Vorteil an Schorns Beweis gegenüber den Beweisen von Euklid und Stieltjes ist, dass man bei ihm nur von einer bestimmten Anzahl von Primzahlen, nicht aber von konkreten Primzahlen ausgeht.

Goldbachs Beweis (1730)

Wenn man eine unendliche Folge natürlicher Zahlen $a_{1},a_{2},\ldots ,a_{n},\ldots$ finden kann, die paarweise teilerfremd sind, dann existiert eine Folge von Primzahlen $p_{1},p_{2}\ldots ,p_{n},\ldots$, für die gilt, dass die Primzahlen $p_{i}$ die natürliche Zahlen $a_{i}$ teilen. Diese Primzahlen sind dann alle verschieden. Wenn man also eine solche Folge findet, dann gibt es auch eine unendliche Anzahl von Primzahlen.

Es gibt eine solche Folge natürlicher Zahlen, die paarweise teilerfremd sind: die Folge der Fermat-Zahlen $F_{n}=2^{2^{n}}+1$ für $n\geq 0$. Es gilt nämlich $F_{m}-2=F_{0}\cdot F_{1}\cdot \ldots \cdot F_{m-1}$. Dieser Satz lässt sich per vollständiger Induktion zeigen. Daraus folgt für $n<m$, dass $F_{n}$ die Zahl $F_{m}-2$ dividiert. Angenommen eine Primzahl $p$ würde die beiden Fermat-Zahlen $F_{n}$ und $F_{m}$ dividieren, dann würde sie auch $F_{m}-2$ und $F_{m}$ dividieren. Daraus würde $p=2$ folgen. Da aber jedes $F_{n}$ ungerade und damit nicht durch 2 teilbar ist, ist jedes Glied dieser Folge teilerfremd zu allen anderen.

Bertrands Postulat

Bertrands Postulat besagt: Für $n>1\$ gilt, daß zwischen $n\$ und $2n\$ wenigstens eine Primzahl liegt. Nun kann man die unendliche Folge der Natürlichen Zahlen in unendlich viele Abschnitte aufteilen: 2 bis 4; 5 bis 10; 11 bis 22; 23 bis 46; 47 bis 94; 95 bis 190; ... . In jedem dieser unendlich vielen Abschnitte muß wenigstens eine Primzahl liegen. Demzufolge müssen unendlich viele Primzahlen existieren.

_{Quelle: Die Primzahlbeweise von Thomas Jean Stieltjes, Schorn und Christian Goldbach sind aus dem Artikel Primzahl (Beweise) von der deutsprachigen de.wikipedia.org entnommen. Als ursprüngliche Quelle diente das Buch: The New Book of Prime Number Records, 3. Aufl., Springer Verlag von Paolo Ribenboim.}

Die abzählbare Unendlichkeit

Die Primzahlen bilden eine unendliche Teilmenge der Menge $N$ der Natürlichen Zahlen, und sind deshalb abzählbar unendlich.

Primzahlen

Eine Primzahl ist eine natürliche Zahl größer Eins, die nur durch die Eins und sich selbst teilbar ist

Die naheliegenste Methode zu testen, ob es sich bei einer natürlichen Zahl $n$ um eine Primzahl handelt, ist, zu prüfen, ob es eine natürliche Zahl $t$ mit $2\leq t\leq n-2$ gibt, die $n$ teilt. Zu prüfen, ob $n$ von $n-1$ geteilt wird, ist überflüssig, da $n$ und $n-1$ in jedem Fall teilerfremd sind.

Ein Programm dazu:

do forever
  say "Bitte gib eine natürliche Zahl ein (Programm beenden mit 0):"
  pull n
  if (n = 0) then leave
  t = 0
  do i = 2 to n-2
    if ((n // i) = 0) then t = 1
  end
  if (t = 0) then say "Die Zahl "||n||" ist eine Primzahl"
  if (t = 1) then say "Die Zahl "||n||" ist keine Primzahl"
end

Verbesserungsmöglichkeiten des konsequenten Durchtesten

Man kann das Verfahren des konsequenten Durchtesten auf unterschiedliche Arten verbessern:

• Wenn aus einem beliebigen Produkt $a\cdot b=n$ mit $a<b$ der Faktor $a$ schon als Teiler getestet wurde, so ist es nicht mehr nötig, Faktor $b\$ auch noch zu testen.

Angenommen ich teste die Zahl 35 = 5·7 auf ihre primalität. Wenn ich die 5 getestet und festgestellt habe, das sie ein Teiler von 35 ist, kann ich aufhören, weitere Zahlen darauf zu testen, ob sie Faktoren der 35 sind oder nicht. Um mal den Extremfall zu zeigen: Angenommen ich will 49 auf ihre primalität testen. Dann muß ich das nur bis zur 7 machen, weil 7 die Quadratwurzel von 49 ist: 7·7 = 49.

Wie sieht das nun bei einer Primzahl aus? Wie weit muß ich da testen? Bis $n-2$? Nein, es reicht, bis $\left\lfloor {\sqrt {n}}\right\rfloor$ zu testen. Warum?

Angenommen, es gibt keinen Teiler kleiner $\left\lfloor {\sqrt {n}}\right\rfloor$, der $n$ teilt. Dann kann es auch keinen Teiler größer $\left\lfloor {\sqrt {n}}\right\rfloor$ geben, der $n$ teilt. Warum?

Nehmen wir mal an, wir haben zwei natürliche Zahlen $\left\lfloor {\sqrt {n}}\right\rfloor <a\leq b$ für die gilt $a$ teilt $n$ und $b$ teilt $n$. Daraus würde folgen, das $(\left\lfloor {\sqrt {n}}\right\rfloor )^{2}=n<a\cdot b$ ist. Das ist ein Widerspruch, und deshalb muß man auch nur bis maximal $\left\lfloor {\sqrt {n}}\right\rfloor$ testen.

• Primzahlen größer 3 haben die Form $6k+1$ oder $6k-1$

Aus diesem Grund braucht man Primzahlen, die nicht dieser Form entsprechen nicht kosequent auf alle mögliche Teiler zu testen. Es reicht, einen Vortest auf die Formen $6k+1$ und $6k-1$ zu machen. Zahlen die nicht diesen Formen entsprechen, fallen als Kandidaten für Primzahlen gleich raus. Das sind ${\tfrac {2}{3}}$ aller natürlichen Zahlen.

Ein Programm, das alle Verbesserungen berücksichtigt, könnte so aussehen:

do forever
  say "Bitte gib eine natürliche Zahl ein (Programm beenden mit 0):"
  pull n
  if (n = 0) then leave
  t = 1
  t2 = ((n-1)//6)*((n+1)//6)
  t3 = (n-2)*(n-3)
  if ((n > 3) && (t2 = 0)) then do
    t = 0
    do i = 2 to sqrt(n)
      if ((n // i) = 0) then t = 1
    end
  end
  if (t3 = 0) then t = 0
  if (t = 0) then say "Die Zahl "||n||" ist eine Primzahl"
  if (t = 1) then say "Die Zahl "||n||" ist keine Primzahl"
end

Serie

Angenommen, man möchte einen ganzen Bereich von 1 bis zu einer bestimmten Oberzahl auf Primzahlen durchsuchen. Dann wäre es nicht sinnvoll, so man das konsequente Durchtesten verwenden würde, immer wieder mit Null anzufangen. Also so ein Programm:

say "Bitte gib eine Obergrenze ein:"
pull n
do i2 = 2 to n
  if (n = 0) then leave
  t = 1
  t2 = ((n-1)//6)*((n+1)//6)
  t3 = (n-2)*(n-3)
  if ((n > 3) && (t2 = 0)) then do
    t = 0
    do i = 2 to sqrt(n)
      if ((n // i) = 0) then t = 1
    end
  end
  if (t3 = 0) then t = 0
  if (t = 0) then say n
end
pull x

wäre nicht sinnvoll. Besser ist es, schon gefundene Primzahlen im Programm zu speichern:

Wenn man testen möchte, ob eine natürliche Zahl $n$ eine Primzahl ist, kommt einem vielleicht als erstes das Konsequente Durchtesten auf Teilbarkeit in den Sinn. Dabei testet man, ob es eine natürliche Zahl zwischen 2 und $n-1$ gibt, die $n$ teilt. Existiert keine natürliche Zahl zwischen 2 und $n-1$ gibt, die $n$ teilt, so ist $n$ eine Primzahl. Findet sich wenigstens eine Zahl zwischen 2 und $n-1$ die $n$ teilt, so ist $n$ keine Primzahl.

Das Sieb des Eratosthenes

Das Sieb des Eratosthenes ist ein altes Verfahren, um alle Primzahlen zwischen 2 und einer fest vorgebenen Obergrenze aus den natürlichen Zahlen herauszufiltern. Dabei speichert man alle Zahlen zwischen 2 und Obergrenze in ein Array und markiert sie als Primzahlen. Dann beginnt das Sieben: Die kleinste Zahl, die als Primzahl markiert ist wird herausgesucht (das ist zu Anfang die 2), nun werden alle Vielfachen der Primzahl, beginnend mit dem Quadrat der Primzahl als Nichtprimzahlen markiert. Nach diesem Durchlauf, wird die nächstgrößere Zahl herausgesucht, die als Primzahl markiert ist. Das Ganze läuft solange ab, bis die nächste Zahl größer als ${\sqrt {\text{Obergrenze}}}$ ist. Alle Zahlen, die jetzt noch als Primzahlen markiert sind, sind auch Primzahlen.

obergrenze=10000
/* Initialisierung des Primzahlfeldes: Alle Zahlen größer gleich 2 */
/* sind Primzahlen                                                 */
do i=2 to obergrenze
  primzahlfeld.i=1
end
/* Der Siebprozess beginnt hier */
do i=2 to sqrt(obergrenze)
  if (primzahlfeld.i=1) then
  do i2=i*i to n by i
    primzahlfeld.i2=0
  end
end
/* Hier werden die Primzahlen ausgegeben */
do i=2 to n
  if (primzahlfeld.i=1) then say i;", "; 
end

Primzahlen

Primfaktorzerlegung

Einleitung

Angenommen, man hat eine Zahl vor sich, z.B. 7657 und möchte nun die Teiler dieser Zahl bestimmen. Mal vorausgesetzt, es handelt sich um keine Primzahl, kann man anfangen, die Zahl auf einzelne Teiler zu testen:

Die letzte Ziffer ist 7, also ist sie weder durch 2 noch durch 5 teilbar. Die Quersumme ist 25, die nicht durch 3 teilbar ist, und damit ist 7657 auch nicht durch 3 teilbar.

Durch 7 dividiert ergibt 7657 als Ergebnis 1093 Rest 6. Folglich ist 7657 auch nicht durch 7 teilbar. Machen wir es kurz: 7657 ist auch nicht durch 11, 17, 23 und 29 teilbar. Die Primfaktorzerlegung von 7657 ist 13·19·31.

Um die Primfaktorzerlegung zu Automatisieren, kann man nun, rein theoretisch, die Teilbarkeit durch eine Liste von Primzahlen testen, die in dem Programm fest vorgegeben ist. Das hat zwei Nachteile:

1. Das Programm wird dadurch ziemlich groß.
2. Es besteht immer die Möglichkeit, dass die Zahl, zu der die Primfaktorzerlegung durchgeführt werden soll, Primfaktoren enthält, die in dem Programm nicht vorhanden sind.

Die Mutter aller Faktorisierungsverfahren

Es gibt ein Verfahren, mit dem man diese Probleme umgehen kann. Dieses Verfahren heißt nach dem französischen Amateurmathematiker Pierre de Fermat die Primfaktorzerlegung nach Fermat. Aber zuerst ein paar Überlegungen:

Eine zusammengesetzte, ungerade natürliche Zahl $n$ läßt sich als Produkt zweier ungerade natürlicher Zahlen $t_{1}$ und $t_{2}$ darstellen:

$n=t_{1}\cdot t_{2}$

Man kann, unter der Bedingung $t_{2}<t_{1}$, zwei natürliche Zahlen $a$ und $b$ mit $b<a$ finden, so dass $t_{1}=a+b$ und $t_{2}=a-b$ gilt, nämlich als Lösung eines linearen Gleichungssystems mit den Variablen $a,$ und $b$. Über die dritte binomische Formel kommt man zu der Gleichung $n=a^{2}-b^{2}$:

$n=t_{1}\cdot t_{2}=\left({\frac {t_{1}+t_{2}}{2}}\right)^{2}-\left({\frac {t_{1}-t_{2}}{2}}\right)^{2}=a^{2}-b^{2}$

Man kann $n$ also auch als Differenz zweier Quadrate ansehen Das ist die Grundlage für die Primfaktorzerlegung nach Fermat: Wenn man eine Quadratzahl $a$ findet, so dass für $a^{2}-n=r$ auch $r$ ein Quadrat ist $(r=b^{2}),$ so kann man zwei Teiler bestimmen.

Bei dem Fermatschen Verfahren sind ein paar Dinge zu beachten:

1. Das fermatsche Verfahren kann nur ungerade Zahlen faktorisieren. Zweierpotenzen sind also vor der Primfaktorisierung zu entfernen.
2. Das fermatsche Verfahren kann Quadrate nicht von Primzahlen unterscheiden (dazu später mehr).

Der Bereich des Fermatschen Verfahren läßt sich eingrenzen:

Man beginnt bei dem kleinsten $a$ mit $a^{2}>n.$ Die obere Grenze liegt bei $a={\frac {n-1}{2}}+1,$ so dass $b={\frac {n-1}{2}}$ ist.

Die Effizienz des Faktorisierungsverfahren nach Fermat hängt vom Aufbau der zu testenden Zahl ab. Es folgen ein ideales und ein negatives Beispiel.

Das ideale Beispiel

Zu faktorisieren ist die Zahl 19043. Die untere Grenze liegt bei $a=138$ und die obere Grenze bei $a=9522.$ Schon bei

$138^{2}-19043=19044-19043=1$

findet man ein Quadrat, was die Zerlegung

$19043=138^{2}-1^{2}=(138+1)(138-1)=139\cdot 137$

liefert.

Wie man sehen kann, liegt der kleinste positive Treffer $a^{2}-n=b^{2}$ mit $a=138$ bei der unteren Grenze. Und nicht nur das, er liefert auch gleich die vollständige Primfaktorzerlegung 19043 = 137·139 zurück. Dass dies so ist, liegt daran, dass die Zahl nur aus zwei Primfaktoren besteht und außerdem die beiden Primfaktoren dicht beieinander liegen.

Die obere Grenze führt noch zu:

$9522^{2}-19043=90668484-19043=90649441=9521^{2},$

was die Zerlegung

$19043=9522^{2}-9521^{2}=(9522+9521)(9522-9521)=19043\cdot 1$

liefert.

So ein Fall kommt eher selten vor; deshalb folgt noch das Negativbeispiel.

Das negative Beispiel

Zu faktorisieren ist die Zahl 12341. Die untere Grenze liegt bei $a=112$ und die obere Grenze bei $a=6170.$

$112^{2}-12341=12544-12341=203$ ist kein Quadrat,

$113^{2}-12341=12769-12341=428$ ist kein Quadrat,

und so weiter. Erst bei

$165^{2}-12341=27225-12341=14884=122^{2}$

findet man ein Quadrat, was die Zerlegung

$12341=165^{2}-122^{2}=(165+122)(165-122)=287\cdot 43$

liefert.

Die weiteren Prüfungen liefern (nur) für die Zahlen 171, 885 und 6171 Treffer. Diese Zahlen führen zu folgenden Zerlegungen:

${\begin{aligned}12341&=171^{2}-130^{2}&&=(171+130)(171-130)&&=287\cdot 43\\12341&=885^{2}-878^{2}&&=(885+878)(885-878)&&=1763\cdot 7\\12341&=6171^{2}-6170^{2}&&=(6171+6170)(6171-6170)&&=12341\cdot 1\\\end{aligned}}$

Erst bei $a=165$ liefert die Gleichung $a^{2}-n=b^{2}$ den ersten positiven Treffer. Das bedeutet, es müssen 53 Quadratzahlen getestet werden, bis der erste Treffer gefunden wird. Demgegenüber findet man beim Divisionsverfahren schon mit der vierten Primzahl (der 7) einen Teiler. Noch schlechter ist, dass 12341 = 287·43 nicht die komplette Primfaktorisierung zurückliefert.

Man braucht alle drei Treffer, um alle Primfaktoren zu ermitteln, und erst ein Kreuzvergleich über den größten gemeinsamen Teiler mit allen Teilergebnissen bringt Sicherheit.

Primzahlen

Einleitung

Es sind häufig zwei Fragen, die sich in Bezug auf die Primzahlen stellen:

1. Ist die vorliegende Zahl eine Primzahl?
2. Wie läßt sich die vorliegende Zahl zerlegen?

Ist die vorliegende Zahl eine Primzahl?

Wenn die vorliegende Zahl sehr klein ist, also kleiner als 90, dann kann man schon mit etwas Überlegung sagen, ob es sich um eine Primzahl handelt, oder nicht. Die 91 ist der erste kleine Stolperstein, da sie die erste Zahl ist, deren sämtliche Primfaktoren größer als fünf sind (91=7·13). Wer allerdings Primzahlen auswendig weiß, kann durchaus bis 127 und höher kommen. Aber wer lernt schon vier- oder mehrstellige Primzahlen auswendig (333667 mag da, z.B. wegen ihrer Eigenschaften, eine Ausnahme sein). Also braucht man ein Verfahren, um solche Zahlen auf ihre Primalität zu testen.

• Primzahlen: naive Ansätze

Probabilistische Verfahren

• Fermat
• Solovay-Strassen
• Miller-Rabin

Sonderfall Sieb des Eratosthenes

Das Sieb des Eratosthenes ist ein Sonderfall. Im Gegensatz zu Verfahren, die einzelne Zahlen auf ihre Primalität prüfen, siebt das Siebverfahren aus einem vorgegebenen Zahlenbereich, von 2 bis zu einer vorgegebenen Obergrenze, alle Nichtprimzahlen aus, so dass nur die Primzahlen übrig bleiben. Dabei wird wie folgt vorgegangen. Jede natürliche Zahl zwischen 2 und der Obergrenze bekommt eine Art kleines Schild, auf der ihr Zustand bezüglich der Primalität geschrieben steht. Am Anfang werden alle Zahlen zwischen 2 und Obergrenze als Primzahl deklariert. Nun wird die erste Zahl genommen, das ist die 2, und nachgesehen, ob es eine Primzahl ist. Die 2 hat die Information Primzahl. Wenn also die 2 eine Primzahl ist, dann können alle Vielfachen von 2, angefangen mit 2² keine Primzahlen mehr sein. Dementsprechend wird auf allen Schildern der Vielfachen von 2, angefangen mit 2² bis Obergrenze, die Information von Primzahl auf Nichtprimzahl geändert. danach wird die nächste Zahl, das ist die 3, auf ihre Primalität getestet. Wieder werden, im Falle, dass es sich um eine Primzahl handelt alle Vielfachen in ihrem Zustand von Primzahl auf Nichtprimzahl geändert. Das Ganze wird solange gemacht, bis man die Quadratwurzel von Obergrenze erreicht hat, weswegen es sinnvoll ist, als Obergrenze eine Quadratzahl einzusetzen. Wenn man z.B. ein Zahlenfeld von 2 bis 10.000 siebt, dann muß man nur bis 100 testen, da 100² = 10.000 ist. Alle Zahlen größer 100, die noch auf ihrem Schild Primzahl stehen haben, sind auch Primzahlen.

Der Sinn des Sieb des Eratosthenes ist, Primzahltabellen zu erstellen, in denen man - bei kleineren Zahlen - nachsehen kann, ob es sich bei der gesuchten Zahl um eine Primzahl handelt. Im Anhang findet man mit Primzahlen: Tabelle der Primzahlen (2 - 100.000) eine Primzahltabelle (bzw. einen Teil einer Primzahltabelle), die mit einem Programm, das den Algorithmus Sieb des Eratosthenes benutzt, generiert worden ist.

Wie ist die Primfaktorzerlegung?

• Primzahlen: Primfaktorzerlegung nach Fermat
• Primfaktorzerlegung nach Lehman

Primzahlen

Einleitung

In diesem Kapitel geht es um die Verteilung der Primzahlen

Die abzählbare Unendlichkeit

Wie im II. Kapitel: Die Unendlichkeit der Primzahlen gezeigt, bilden die Primzahlen eine abzählbar unendliche Teilmenge der Natürlichen Zahlen. Die Menge $P$ der Primzahlen lässt sich also abzählen:

$P=\{p_{1},p_{2},p_{3},\ldots \}.$

Eine mögliche Zuordnung wäre:

$p_{1}=2,\ p_{2}=3,\ p_{3}=5,\ p_{4}=7,\ p_{5}=11,\ p_{6}=13,\ p_{7}=17,\ \ldots$

Die Primzahl-Funktion

Die Funktion $\pi (n)$ gibt die Anzahl aller Primzahlen bis zu einer vorgegebenen Grenze $n$ an. So gibt es unter 100 25 Primzahlen, und demzufolge ist $\pi (100)=25$. Aber wie lässt sich $\pi (n)$ berechnen?

Mindestens so: $\pi (n+1)=\pi (n)$ falls $n+1$ keine Primzahl ist und $\pi (n+1)=\pi (n)+1$ falls $n+1$ Primzahl

• Beispiel

n	π(n)
10	4
100	25
1000	168
10.000	1229
100.000	9592
1.000.000	78498

Der Primzahlsatz

Der Primzahlsatz besagt, wie sich die Primzahl-Funktion asymptotisch verhält. Es zeigt sich, dass $\pi (n)$ sich asymptotisch verhält wie die Funktion $n/{\ln(n)}$, d. h. die Funktionen $\pi (n)$ und $n/{\ln(n)}$ sind asymptotisch äquivalent. Formel:

$\lim _{n\to \infty }{\frac {\pi (n)}{\frac {n}{\ln(n)}}}=1.$

Eine noch bessere Approximation als ${\tfrac {n}{\ln(n)}}$ ist der Integrallogarithmus

$\mathrm {Li} (n):=\int _{2}^{n}{\frac {\mathrm {d} t}{\ln t}}.$

Die Ableitung des Integrallogarithmus ist eine Näherung für die Wahrscheinlichkeit, dass eine ganze Zahl $n>7$ eine Primzahl ist:

$P(n)={\frac {1}{\ln(n)}}$ und

$P_{odd}(n)={\frac {2}{\ln(n)}}$ für ungerade Zahlen $n>7$.

Primzahlen

Einleitung

In diesem Kapitel geht es um die Lücken zwischen zwei Primzahlen und deren Größe.

Primzahllücken

Was versteht man unter einer Primzahllücke? Das ist ganz einfach. Eine Primzahllücke ist der Abstand zwischen zwei aufeinanderfolgenden Primzahlen. Als Länge der Primzahllücke bezeichnet man die Differenz zweier aufeinanderfolgender Primzahlen. Die bekannteste Form der Primzahllücken sind die Primzahlzwillinge, zwei Primzahlen $\ p_{1}\$ und $\ p_{2}=p_{1}+2$, zwischen denen genau eine Nichtprimzahl liegt.

Gibt es die Möglichkeit, Primzahllücken einer bestimmten Mindestlänge zu konstruieren?

Ja, die Möglichkeit gibt es. Hier werden drei Vorgehensweisen vorgestellt:

Konstruktion einer Primzahllücke über die Fakultät:

Die Fakultät $n!\$ hat die folgende Eigenschaft, dass sie durch alle Zahlen von 2 bis n teilbar ist. Demzufolge ist eine Zahl $n!+m\$ mit $2\leq m\leq n$ auch durch $m\$ teilbar, und damit keine Primzahl. Auf diese Weise bekommt man eine feste Lücke aus $n-1\$ Nichtprimzahlen zwischen $n!+2\$ und $n!+n\$.

Beispiel:

n=6

$6!+2=722$ ist durch 2 teilbar.

$6!+3=723$ ist durch 3 teilbar.

$6!+4=724$ ist durch 4 teilbar.

$6!+5=725$ ist durch 5 teilbar.

$6!+6=726$ ist durch 6 teilbar.

Konstruktion einer Primzahllücke über das kgV

Das folgende Verfahren ist mit der Konstruktion über die Fakultät verwandt. Das $\operatorname {kgV} (2,\dots ,n)$ ist, wie die Fakultät $n!$, durch alle Zahlen zwischen 2 und n teilbar. Wie bei dem Verfahren mit der Fakultät gilt, dass das $\operatorname {kgV} (2,\dots ,n)+m$ mit $2\leq m\leq n$ durch $m$ teilbar ist, und damit keine Primzahl sein kann. Und genauso wie bei dem Verfahren mit der Fakultät bekommt man eine feste Lücke aus $n-1$ Nichtprimzahlen zwischen $\operatorname {kgV} (2,\dots ,n)+2$ und $\operatorname {kgV} (2,...,n)+n$.

Beispiel:

n=6

$\operatorname {kgV} (2,\dots ,6)+2=62$ ist durch 2 teilbar.

$\operatorname {kgV} (2,\dots ,6)+3=63$ ist durch 3 teilbar.

$\operatorname {kgV} (2,\dots ,6)+4=64$ ist durch 4 teilbar.

$\operatorname {kgV} (2,\dots ,6)+5=65$ ist durch 5 teilbar.

$\operatorname {kgV} (2,\dots ,6)+6=66$ ist durch 6 teilbar.

Konstruktion einer Primzahllücke über das Primorial

Dieses Verfahren ist etwas subtiler. Es beruht auf einer mathematischen Operation, die im englischen primorial genannt wird. Das primorial $p_{n}\#$ ist das Produkt aller Primzahlen zwischen 2 und $p_{n}$. Hierbei ist nicht sichergestellt, dass alle natürlichen Zahlen zwischen 2 und $p_{n}$ als Teiler vorhanden sind. Aber dies ist auch gar nicht nötig, denn alle Zahlen zwischen 2 und $p_{n+1}-1$ können nur Primzahlen zwischen 2 und $p_{n}$ als Faktoren enthalten.

Beispiel:

n=5 (bis $5\#+6$, da erst 7 die nächst höhere Primzahl ist)

$5\#+2=32$ ist durch 2 teilbar.

$5\#+3=33$ ist durch 3 teilbar.

$5\#+4=34$ ist durch 2 teilbar.

$5\#+5=35$ ist durch 5 teilbar.

$5\#+6=36$ ist durch 6 teilbar.

Einschränkung

Keines der genannten Verfahren garantiert, dass die direkt an die Lücke grenzenden Zahlen Primzahlen sind. Die eigentliche Lücke kann in Wirklichkeit wesentlich größer sein:

Beispiele:

n=8

$8!+2=40322$ ist durch 2 teilbar.

$8!+3=40323$ ist durch 3 teilbar.

$8!+4=40324$ ist durch 4 teilbar.

$8!+5=40325$ ist durch 5 teilbar.

$8!+6=40326$ ist durch 6 teilbar.

$8!+7=40327$ ist durch 7 teilbar.

$8!+8=40328$ ist durch 8 teilbar.

Die nächsten Primzahlen sind allerdings erst 40289 und 40343, und damit liegen 53 statt nur 7 Nichtprimzahlen in der Lücke.

n=11

$\operatorname {kgV} (2,\dots ,11)+\ 2=27722$ ist durch 2 teilbar.

$\operatorname {kgV} (2,\dots ,11)+\ 3=27723$ ist durch 3 teilbar.

$\operatorname {kgV} (2,\dots ,11)+\ 4=27724$ ist durch 4 teilbar.

$\operatorname {kgV} (2,\dots ,11)+\ 5=27725$ ist durch 5 teilbar.

$\operatorname {kgV} (2,\dots ,11)+\ 6=27726$ ist durch 6 teilbar.

$\operatorname {kgV} (2,\dots ,11)+\ 7=27727$ ist durch 7 teilbar.

$\operatorname {kgV} (2,\dots ,11)+\ 8=27728$ ist durch 8 teilbar.

$\operatorname {kgV} (2,\dots ,11)+\ 9=27729$ ist durch 9 teilbar.

$\operatorname {kgV} (2,\dots ,11)+10=27730$ ist durch 10 teilbar.

$\operatorname {kgV} (2,\dots ,11)+11=27731$ ist durch 11 teilbar.

Die nächsten Primzahlen sind allerdings erst 27701 und 27733, und damit liegen 31 statt nur 10 Nichtprimzahlen in der Lücke.

n=11

$11\#+\ 2=2312$ ist durch 2 teilbar.

$11\#+\ 3=2313$ ist durch 3 teilbar.

$11\#+\ 4=2314$ ist durch 2 teilbar.

$11\#+\ 5=2315$ ist durch 5 teilbar.

$11\#+\ 6=2316$ ist durch 6 teilbar.

$11\#+\ 7=2317$ ist durch 7 teilbar.

$11\#+\ 8=2318$ ist durch 2 teilbar.

$11\#+\ 9=2319$ ist durch 3 teilbar.

$11\#+10=2320$ ist durch 10 teilbar.

$11\#+11=2321$ ist durch 11 teilbar.

Die nächsten Primzahlen sind allerdings erst 2311 und 2333, und damit liegen 21 statt nur 10 Nichtprimzahlen in der Lücke.

• Primzahlen: VI. Kapitel: Verschiedene Primzahl-Arten
• Primzahlen: VII. Kapitel: Primzahlgeneratoren

Primzahlen

Einleitung

Die Sache, um die es hier geht, ist mit der Fakultät verwandt, also mit dem Produkt aller natürlichen Zahlen zwischen 1 und n:

$\prod _{i=1}^{n}i=1\cdot 2\cdot 3\cdot \ldots \cdot n=n!$

Das Produkt aller Primzahlen bis zu einer vorgegebenen Grenze wird mit $n\#$ ausgedrückt, wobei es zwei verschiedene Lesarten gibt:

Definition 1:

$p_{n}$ ist eine Primzahl, und $p_{n}\#$ ist das Produkt der Primzahlen von $p_{1}$ bis $p_{n}$.

Beispiel: $5\#=2\cdot 3\cdot 5=30$

Definition 2:

$n\#$ ist das Produkt der ersten $n$ Primzahlen.

Beispiel: $5\#=2\cdot 3\cdot 5\cdot 7\cdot 11=2310$

Wenn in diesem Buch von $p\#$ die Rede ist, dann bezieht sich das auf die erste Definition.

Eine andere Sache ist die Benennung dieser Operation. Im englischen Sprachraum etabliert sich die Bezeichnung primorial (Verschmelzung von prime für Primzahl und factorial für Fakultät), im Deutschen müsste es logischerweise Primultät (Verschmelzung von Primzahl und Fakultät) heißen. Die Ausdrücke Primzahlfakultät und Primfakultät sind Kompromisse.

Welche Bezeichnung sich in Zukunft im deutschen Sprachraum durchsetzen wird, wird die Zukunft zeigen. Und da ja auch wenigstens zwei Definitionen für die Operation $n\#$ existieren, wird man bei der Verwendung von $n\#$ immer angeben müssen, auf welche Definition sie sich bezieht.

Anhänge

• Primzahlen: zeitliche Abfolge

Primzahlen

 Eratosthenes

Eratosthenes von Kyrene (auch Erathostenes genannt) (* ca. 284 v. Chr. in Kyrene; † 202 v. Chr. in Alexandria war ein griechischer Mathematiker sowie Direktor der Bibliothek von Alexandria. Nach Eratosthenes ist das Sieb des Eratosthenes benannt, einem Verfahren, mit dem man aus einem endlichen Zahlenfeld die Primzahlen heraussieben kann. Auf diese Weise lassen sich Primzahltabellen erstellen.

 Euklid

Euklid war ein griechischer Mathematiker der ca. 300 v. Chr. in Alexandria lebte. Auf Euklid geht der Satz von Euklid zurück, dem ersten bekannten Beweis, dass keine größte Primzahl existiert, und damit unendlich viele Primzahlen existieren.

 Leonhard Euler

(* 15. April 1707 in Riehen (Schweiz), † 18. September 1783 in St. Petersburg)

 Pierre de Fermat

Pierre de Fermat (* Ende 1607 oder Anfang 1608 in Beaumont-de-Lomagne, † 12. Januar 1665 in Castres) war ein französischer Jurist und Amateurmathematiker. Seine besonderen Leistungen liegen im kleinen fermatschen Satz und dem großen fermatschen Satz - der Behauptung, dass es für $a^{n}+b^{n}=c^{n}$ keine ganzzahlige Lösung mit $n>2$ gibt. Diese Vermutung wurde erst Ende des 20. Jahrhunderts, also nach mehr als 300 Jahren bewiesen.

Pierre de Fermat vermutete, dass alle Zahlen der Form $F_{n}=2^{2^{n}}+1$ Primzahlen sind. Diese Vermutung wurde 1732 von Leonhard Euler widerlegt. Nach Fermat heißt diese Art von Zahl Fermat-Zahl; mit $n\leq 4$ sind diese Zahlen tatsächlich Primzahlen und werden Fermatsche Primzahlen genannt. Der deutsche Mathematiker Christian Goldbach hat die Fermat-Zahl für einen Beweis, dass es unendlich viele Primzahlen geben muss, verwendet.

Primzahlen

Primzahlsatz

Anzahl der Primzahlen $(\pi (n))\$kleiner gleich $n$:

$\lim _{n\to \infty }{\frac {\pi (n)}{\frac {n}{\ln(n)}}}=1$

${\pi (n)}\approx {\frac {n}{\ln(n)}}$ mit $n>7$

Eine noch bessere Approximation als ${\tfrac {n}{\ln(n)}}$ ist der Integrallogarithmus

$\pi (n)\approx \mathrm {Li} (n):=\int _{2}^{n}{\frac {\mathrm {d} t}{\ln t}}.$

Wahrscheinlichkeit, dass eine ganze Zahl $n>7$ eine Primzahl ist:

$P(n)\approx {\frac {1}{\ln(n)}}$

Binomialkoeffizient

Der Binomialkoeffizient kommt aus der Wahrscheinlichkeitsrechnung. Mit Hilfe des Binomialkoeffizienten lässt sich berechnen, wieviele Möglichkeiten es gibt m Objekte aus einer Gesamtzahl von n unterschiedlchen Objekten auszuwählen. Berechnet wird der Binomialkoeffizient nach der Formel:

${n \choose m}={\frac {n\cdot n-1\cdot n-2\cdot ...\cdot n-(m-1)}{1\cdot 2\cdot 3\cdot ...\cdot m}}={\frac {n!}{m!\cdot (n-m)!}}$

Beispiele

Man hat in einem Beutel sechs farbige Kugeln (rot, grün, blau, gelb, magenta, cyan). Wieviele unterschiedliche Kombinationen zweier Kugeln lassen sich aus dem Beutel nehmen?

${6 \choose 2}={\frac {6\cdot 5}{1\cdot 2}}=15$

Es gibt 15 Kombinationen.

Das bekannteste Beispiel für einen Binomialkoeffizienten ist das Lotto 6 aus 49. Wieviele Kombinationen von 6 Zahlen kann man aus 49 Zahlen zusammenstellen?

${49 \choose 6}={\frac {49\cdot 48\cdot 47\cdot 46\cdot 45\cdot 44}{1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6}}=13983816$

Es sind 13.983.816 (das sind fast 14 Millionen).

Primzahlen

• Primzahlen: Tabelle der Primzahlen (2 - 100.000)
• Primzahlen: Tabellen verschiedener Primzahlarten
• Primzahlen: Primzahllücken
• Primzahlen: Liste_besonderer Primzahlen

Primzahlen

Sieb des Eratosthenes

Die Spezifikation des Algorithmus in Pseudocode ist in der Wikipedia zu finden.

Prinzip

Das Sieb des Eratosthenes ist ein Verfahren, um alle natürlichen Zahlen (ferner nur mit „Zahlen“ bezeichnet) bis zu einer vorgegebenen Zahl n, einschließlich n selbst, auf Primalität zu testen (zu Primzahlen siehe auch die Seite Primfaktorisierung) und, sofern sie prim sind, auszugeben. Das Sieb des Eratosthenes "zäumt das Pferd von hinten auf": Es werden alle Zahlen bis n (inklusive) größer als 1 hintereinander aufgeschrieben. Dann werden die Zahlen der Reihe nach durchgegangen. Die echten Vielfachen der aktuellen Zahl (für 3 z. B. 6, 9, 12, ...) werden durchgestrichen. Übrig bleiben die Zahlen $x_{i}$, die keine echten Vielfachen einer Zahl echt zwischen 1 und $x_{i}$ sind. Dies sind sämtliche Primzahlen bis zur vorgegebenen Grenze.

Beispiel

Sei $n=10$. Hintereinander werden die Zahlen 2, 3, 4, 5, 6, 7, 8, 9, 10 aufgeschrieben. Die 2 wird betrachtet und ihre echten Vielfachen weggestrichen: 2, 3, 4, 5, 6, 7, 8, 9, 10. Dasselbe für die 3: 2, 3, 4, 5, 6, 7, 8, 9, 10. Übrig sind noch 2, 3, 5 und 7. Dies sind, wie wir überprüfen können, alle Primzahlen im betrachteten Intervall, sodass hier abgebrochen werden kann. Schritte, um das Verfahren zu optimieren, damit der Algorithmus wirklich schon so früh endet, werden im nächsten Absatz besprochen.

Optimierungen eines simplen Durchgehens aller Zahlen und ihrer echten Vielfachen

Es müssen nur die Zahlen bis einschließlich $\lfloor {\sqrt {n}}\rfloor$ betrachtet werden, wobei $\lfloor \rfloor$ den ganzzahligen Anteil (die Abrundungsfunktion) symbolisiert. Denn sei $n>x>\lfloor {\sqrt {n}}\rfloor$, dann gilt für die Vielfachen: $\ p\cdot x\leq n\Longleftrightarrow p\leq {\frac {n}{x}}<{\sqrt {n}}$, alle Vielfachen von $x$ wurden also bereits als Vielfache von $2\leq p<{\sqrt {n}}\$gestrichen.

Bereits gestrichene Zahlen müssen nicht mehr betrachtet werden, da ihre echten Vielfachen garantiert durch einen echten Teiler der gestrichenen Zahl teilbar sind.

Weiter optimieren kann man unter anderem, indem man das Wegstreichen der echten Vielfachen einer Zahl $p$ erst bei $p^{2}$ beginnt. Denn alle Vielfachen $<p^{2}$ sind von der Form $y\cdot p$ mit $y<p$. Damit wurden sie aber als ganzzahlige Vielfachen einer kleineren Zahl schon überprüft.

Komplexitätstheoretische Beschreibung

Durch diese und weitere Optimierungen lässt sich die Laufzeit auf $O(n\log {\log {n}})$ reduzieren. Beim Vergleich verschiedener Implementierungen und Varianten des Algorithmus ist die Ordnung der Laufzeit aber nur bedingt von Nutzen, da sie Konstanten außer Acht lässt. Bei diesem speziellen Problem wird der Sachverhalt bei einem Vergleich verschiedener Varianten auch bei großen n offensichtlich.

Die Speicherplatzkomplexität lässt sich auf $O({\frac {\sqrt {n}}{\log {n}}})$ drücken.

Haskell

Ein einfaches Primzahlsieb in der Programmiersprache Haskell implementiert. Der Speicherbedarf des Algorithmus ist in $O(p~\log _{2}b)$ Bits, wobei $p$ die Anzahl der auszugebenen Primzahlen und $b$ die größte auszugebene Primzahl bezeichnet.

> module Sieve
> where 

> sieb :: [Int] -> [Int]
> sieb (l:ls) = l:sieb[x | x <- ls, mod x l /= 0]

> take_primes n = take n $ sieb [2..]

Ausführen via

# hugs Sieve
oder für eine schnellere Version
# ghc -O2 --make Sieve.lhs
# ghci Sieve

Im Haskell-Interpeter zur Ausgabe der beispielsweise ersten 100 Primzahlen:

Prelude Sieve> take_primes 100

Gambas

Siehe hierzu Gambas:_Rechnen#Primzahlen_berechnen

Visual Basic 3

Dieses Programm liefert die Primzahlen von 1 bis 2100000000

Hinter dem Befehl Berechnen steht der unten folgende Code. Der Code wurde mit vielen Rem Kommentaren versehen. Sie können die rem Kommentare herauswerfen und wahrscheinlich auch die Variable j streichen. Versuchen Sie den Fehler bei der Print Ausgabe mit der Startzahl 1-5 zu eliminieren.

Code

 Sub Befehl1_Click () 
 Cls 
 j = 1 
  Rem Zähler j für die ungeraden Zahlen die keine Primzahlen sind 
  Rem ist wahrscheinlich überflüssig 
  m = text1.Text 
   Rem holt sich aus dem Textfeld1 die erste Zahl zum Testen 
  If m / 2 = Int(m / 2) Then m = m - 1 
    Rem Falls diese Zahl ohne Rest durch 2 teilbar ist, also eine gerade Zahl ist 
    Rem geht das Programm noch eine Zahl rückwärts um eine ungerade Zahl zu bekommen 
  If text1.Text = "" Then m = 6 
    Rem Falls keine Startzahl eingegeben wurde wird die Startzahl m = 6 vergeben. 
  For m = m To m + 1000 Step 2 
   Rem Hauptschleife 
   Rem Die nächsten 1000 ungeraden Zahlen in einer Schleife durchlaufen lassen 
   Rem m ist die Variable für die ungeraden Zahlen 
   f = 1 
   Rem f ist die Variable für die Faktorentestung, 
   Rem m teilbar durch f oder nicht 
   n = m 
   Rem n = ist die Testzahl, bei der noch nicht klar ist ob sie eine Primzahl ist 
   Do While f < Sqr(n) 
    Rem solange der Teiler f kleiner als die Wurzel 
    Rem aus der Testzahl n ist, muß getestet werden 
    f = f + 2 
    Rem Teiler von f = 1 beginnend um jeweils 2 vermehren , 3,5,7,9 etc erster Test also mit f = 3 
    Do While n / f = Int(n / f) 
     Rem Teiler f testen solange bis n / f ohne Rest teilbar 
     Rem Print "m = "; m; " n = "; n; " f = "; f; "j = "; j 
     Rem Wenn Sie bei der letzten Zeile das Rem herauswerfen , 
     Rem erkennen Sie die Bedeutung der Variablen 
     j = j + 1 
     Rem j ist ein Zähler für die ungeraden Zahlen die keine Primzahlen sind 
     Rem j ist wahrscheinlich überflüssig 
     n = Int(n / f) 
     Rem Die Testzahl n verkleinern auf die Zahl n/f 
    Loop 
   Loop 
   A$ = " 1" + Chr(13) + " 2" + Chr(13) + " 3" 
   If m < 7 Then Print A$ 
   Rem Chr(13) = Zeilenwechsel 
   Rem Am Anfang zwischen 1 und 5 gibt es Probleme mit der Ausgabe 
   Rem deswegen werden die ersten drei Zeilen ersetzt durch A$ 
  If n = m Then b = b + 1: Print n: text1.Text = n 
  Rem Wenn die Testzahl n nicht teilbar war durch f 
  Rem ist es eine Primzahl und kann ausgedruckt werden 
  If b = 30 Then m = m + 1000  
  Rem b ist die Zeilennummer, 
  Rem bis Zeile b = 30 werden die berechneten Primzahlen ausgegeben 
  Rem bei Zeile 30 wird die Schleife abgebrochen, 
  Rem da m größer als m + 1000 gesetzt wird 
  Rem wenn ihr Bildschirm die Zahlen nicht mehr komplett anzeigt 
  Rem können Sie für b einen anderen Wert als 30 nehmen 
 Next m 
 Rem Hauptschleife durchlaufen , 
 rem wieder Start am Beginn der Hauptschleife 
 End Sub

Java

Möglichkeit 1

Hier ein möglicher Quelltext eines Java-Programms zur Ausgabe der Primzahlen von 1-100 (Der Bereich kann natürlich beliebig erweitert werden). Die Primzahlen werden dann in der Konsole ausgegeben.

public class Primzahlen {

    public static void main(String[] args) {
        int limit = 100;
        int zahl;      // Zu überprüfende Zahl
        int zaehler;   // Hilfsvariable (möglicher Teiler von zahl)
        boolean primzahl; // Hilfsvariable, ob die aktuelle Zahl eine Primzahl ist

        // zahl <= x   ist der zu überprüfende Zahlenraum
        // Beginn bei 2, weil 1 per Definition keine Primzahl ist
        for (zahl = 2; zahl <= limit; zahl++) {
            // solange wir für zahl keinen Teiler finden, gehen wir davon aus,
            // dass es eine Primzahl ist
            primzahl = true;

            // zaehler ist ein möglicher Teiler. Mögliche nicht-triviale Teiler
            // liegen im Bereich 2 bis zahl/2 (abgerundet), wenn x aber Teiler
            // von Zahl und größer als Wurzel(zahl), ist zahl/x < Wurzel(zahl), 
            // sodass diese Grenze genügt.
            for (zaehler = 2; zaehler < Math.sqrt(zahl) + 1; zaehler++) {
                if (zahl % zaehler == 0) {
                    // zaehler ist ein nichttrivialer Teiler von zahl und damit
                    // zahl keine Primzahl. Weitere Teiler müssen nicht geprüft
                    // werden und damit kann die Schleife abgebrochen werden.
                    primzahl = false;
                    break;
                }


            }

            if (primzahl) {
                // Keine Teiler gefunden -> zahl2 ist eine Primzahl
                System.out.println(zahl+" ist eine Primzahl");
            }
        }
    }
}

Möglichkeit 2

Dies ist eine lauffähige Implementierung der brute-force-Version des Siebes von Eratosthenes mit leichten Optimierungen. Die main()-Funktion lässt sich z. B. zum Testen nutzen. Zuerst wird eine Liste erzeugt, die Map-Einträge enthält, welche eine Zahl und ihren Status (durchgestrichen?) repräsentieren.
Zur Erzeugung eines einzelnen Map-Eintrages brauchte ich das Objekt java.util.AbstractMap.SimpleEntry<K, V>, da Map.Entry als Interface keinen Konstruktor besitzt. Dies ist die eleganteste und schnellste Lösung, ansonsten hätte ich ein komplettes Set mit den Werten erzeugen, dessen Einträge durch Iteration über Set.entrySet() an eine Liste anhängen und diese dann sortieren müssen (bestmögliche Komplexität einer vergleichsbasierten Sortierung: $O(n\log {n})$), da selbst bei Maps, die SortedMap implementieren, entrySet() nicht zwingend sortiert ist.
Nach Abschluss der Durchstreich-Phase werden die noch nicht durchgestrichenen Zahlen in eine Liste geschrieben und als Ergebnis zurückgegeben.

// Benötigt Java 8!

import java.util.*;

public class Primzahlgenerator {

    public static void main(String[] args){

    }

    public static List<Integer> siebDesErasthotenes(int obereGrenze){
        // Prüft sämtliche ganzen Zahlen echt zwischen 1 und der oberen Grenze sowie die obere Grenze selber auf Primalität
        List<AbstractMap.SimpleEntry<Integer, String>> kandidaten = new ArrayList<>();

        List<Integer> ergebnis = new ArrayList<Integer>();

        String gestrichen = "gestrichen";
        String unberuehrt = "unberührt";

        for(int i = 2; i <= obereGrenze; i++){
            kandidaten.add(new AbstractMap.SimpleEntry<>(i, unberuehrt));
        }
       
        int element;
        int index;

        for (int i = 0; i < kandidaten.size() / 2 + 1; i++){
            if (!(kandidaten.get(i).getValue().equals(gestrichen))) {
                element = kandidaten.get(i).getKey();
                index = 2 * element - 2; // Index des nächsten Vorkommens
                while (index < kandidaten.size()) {
                    (kandidaten.get(index)).setValue(gestrichen);  // ArrayList.get in O(1)!
                }
            }
        }
        
        for (Map.Entry<Integer, String> eintrag: kandidaten){
            if (eintrag.getValue() == unberuehrt) {
                ergebnis.add(eintrag.getKey());
            }
        }
        
        return ergebnis;
    }
}

C#

Folgende eigenständig lauffähige Konsolenanwendung (.NET 2.0) gibt alle Primzahlen bis n nach dem Sieb des Eratosthenes aus:

using System;
using System.Collections.Generic;
using System.Text;

namespace eratosthenes
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = 100;
            bool[] prime = new bool[n];
            //Zuerst alle Zahlen von 2 bis n als Primzahl markieren
            for (int i = 2; i < n; i++)
            {
                prime[i] = true;
            }

            //Einzelner Abschnitt
            {
                //Wir wollen bei 2 anfangen
                int i = 2;

                //Alle Produkte des Teilers i
                //angefangen bei 2, bis kleiner n durchlaufen
                //Wenn n = 50, dann ist bei i = 7 Schluss, weil das Produkt = 49 ist
                for (; i * i < n; i++)
                {
                    //Wenn die Zahl im Array als Primzahl markiert ist
                    //Was bei den ersten beiden 2 und 3 definitiv der Fall ist
                    if (prime[i])
                    {
                        //Primzahl bis Wurzel(n) ausgeben
                        Console.WriteLine(i);
                        //Alle weiteren Produkte des Teilers i
                        //angefangen beim Produkt i * i bis kleiner n durchlaufen
                        //j wird mit i beim nächsten Durchlauf (Vielfaches) addiert
                        for (int j = i * i; j < n; j += i)
                        {
                            //Dies kann unmöglich eine Primzahl sein
                            //weil es ein Vielfaches von i ist.
                            prime[j] = false;
                        }
                    }
                }

                //Alle Primzahlen ausgeben
                for (; i < n; i++)
                {
                    if (prime[i])
                    {
                        Console.WriteLine(i);
                    }
                }
            }
            
            Console.ReadLine();
        }
    }
}

Delphi

Folgende Konsolenanwendung gibt mit Hilfe der Funktion isPrim() von einer bestimmten Zahlenmenge die Primzahlen aus.

program Primzahl;

{$APPTYPE CONSOLE}

uses
  SysUtils;

function IsPrim(AInteger: Integer): boolean;
var
  i: Integer;
begin
  result := true;
  if (AInteger <= 1) then  //Wenn Zahl kleiner ist als 2: keine Primzahl
    begin
      result := false;
      exit;               //Funktion beenden
    end;
  for i := 2 to Round(Sqrt(AInteger)) do //Wenn eine Zahl n von 2 bis Wurzel(n)
    begin                                // nicht teilbar ist, ist sie eine Primzahl
      if AInteger mod i = 0 then         //mod: Modulo = Rest
        begin
          result := false;
          exit;
        end;
    end;
end;

var
  a, b: Integer;
  i: Integer;
begin
  Write('von: ');
  Readln(a);       //a abfragen
  Write('bis: ');
  Readln(b);       //b abfragen
  for i := a to b do
      if IsPrim (i) then Writeln(i);    //wenn i eine Primzahl ist: i ausgeben
  Readln;
end.

Python

Theoretisch ein endloser Primzahl-Generator – nur durch die Hardware begrenzt –, aber langsamer als Siebe. Er nutzt den Satz von Wilson in umgestellter Form. Der Programmlauf wird durch Strg-C gestoppt.

#!/usr/bin/python
# -*- coding: utf-8 -*-

import sys, time

def pgen():
  ''' ... generates the sequence of all primes: 2,3,5,7,11 ... 
  '''

  p=2
  f=1

  try:

    ts2=time.time()

    while(True):

      if f%p%2: sys.stdout.write(str(p)+"\n")
      p+=1
      f*=(p-2)

  except:

#   raise KeyboardInterrupt .. Ctrl-C

    ts2-=time.time()
    sys.stderr.write("time: "+str(round(-ts2,3))+" sec\n")

def main():
  pgen()
  sys.exit()

if __name__=="__main__":
  main()

Python 2

Dieses Script bittet den Benutzer zuerst nach einer Obergrenze und gibt danach alle Primzahlen bis zu dieser Grenze aus.

#!/usr/bin/env python
# -*- coding: utf-8 -*-

def main():
    
    # Frage den Benutzer nach einer Obergrenze bis zu der gesucht werden soll
    while True:
        try:
            obergrenze = int(raw_input('Bitte geben Sie eine Obergrenze ein: '))
            break
            
        except ValueError:
            print 'Dies ist keine gültige Obergrenze. Bitte verwenden Sie eine Ganzzahl!'
    
    # Jede Zahl zwischen 1 und obergrenze wird zuerst als prim angenommen
    zahlen = [True]*(obergrenze+1)
    # Da 0 und 1 keine Primzahlen sind, werden sie auf False gesetzt
    zahlen[0] = False
    zahlen[1] = False
    
    i = 2
    
    while i*i <= obergrenze:
        if zahlen[i]: # Die Zahl i ist als prim markiert
            # Streiche alle Vielfachen von i
            for k in range(i*i,obergrenze+1,i):
                zahlen[k] = False
        
        i = i+1
    
    # Ausgabe aller gefundenen Zahlen
    for i, v in enumerate(zahlen):
        if v:
            print i, 'ist prim.'
    
    return 0

if __name__ == '__main__':
    main()

C++

Das Programm fragt zunächst nach einer Obergrenze und gibt dann alle Primzahlen bis zu dieser aus.

#include<iostream>
#include<cmath>
using namespace std;
 
int main(void){
    unsigned limit;
 
    cout << "Please insert upper limit.\n";
    cin >> limit;
 
    bool *Stroke = new bool[limit+1];
    Stroke[0]=1;
    Stroke[1]=1;
    for(unsigned i=2; i<=limit; ++i) Stroke[i] = 0;
 
    unsigned prime=2;
    while(pow((double)prime,2.0)<=limit){
        for(unsigned i = (int)pow((double)prime,2.0); i<=limit; i+=prime){
            Stroke[i]=1;
        }
 
        do ++prime; while(Stroke[prime]);
    }
 
    cout << "\nPrimes less or equal " << limit << " are:\n";
    for(unsigned i=0; i<=limit; ++i){
        if(!Stroke[i]) cout << i << endl;
    }
    delete[] Stroke;

    return 0;
}

Eine andere Variante, die neuere Sprachfeatures (Lambdas, automatische Typableitung - C++11) sowie Container und Algorithmen der Standard Template Library (STL) benutzt, ist die nachfolgende. Dabei wird das Erase-Remove-Idiom benutzt: Der STL-Algorithmus remove_if schiebt alle Elemente des std::vector-Containers, die das durch ein Lambda-Konstrukt ([p](auto q){ ... }) formulierte Teilbarkeits-Kriterium erfüllen, ans Ende des Containers und gibt einen Iterator, der auf den Anfang des zu löschenden Bereiches zeigt, zurück. Mit candidates.erase(..., end(candidates)) schließlich wird der gesamte Bereich gelöscht (was intern lediglich eine Änderung der Längen-Variablen des Containers bedeutet).

#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

vector<unsigned>  primes_upto(unsigned limit)
{
    vector<unsigned>    candidates(limit - 1);
    iota(begin(candidates), end(candidates), 2);    // candidates = 2, 3, ..., n

    auto const  upper_limit = (limit + 1) / 2;      // ceil(limit/2)

    for (auto candidate = begin(candidates);        // vector<unsigned>::iterator
         *candidate <= upper_limit;
         ++candidate)
    {
        auto const p = *candidate;                

        // 'erase-remove idiom':
        // remove_if(...) moves all multiples of p to the end and returns
        // an iterator to the beginning of the (re)moved part;
        // candidates.erase(..., end(candidates)) actually deletes these values
        candidates.erase(remove_if(candidate + 1,   // don't remove p itself
                                   end(candidates),
                                   [p](auto q){     // capture p by value
                                       return (q % p == 0);
                                   }),
                         end(candidates));

    }

    return candidates;      // copy elision guaranteed by C++ standard
}

int main()
{
    unsigned limit;
 
    cout << "Please insert upper limit.\n";
    cin >> limit;

    auto primes = primes_upto(limit);

    for (auto p : primes)
        cout << p << " ";

    cout << endl;
}

R

Limit heißt die Obergrenze, bis zu der alle Primzahlen ausgegeben werden.

sieb<-function(limit){
 (vek<-2:limit)[1==apply(0==outer(vek, vek, "%%"), 1, sum)]
   # Primzahlen bis limit
   # %% Division mit Rest oder modulo
}

Go

Hier ein möglicher Quelltext eines Go-Programms zur Ausgabe der Primzahlen von 1-1000 (Der Bereich kann natürlich beliebig erweitert werden). Die Primzahlen werden dann in der Console ausgegeben. Dieses Programm kann auf der offiziellen Golang-Seite ausprobiert werden. Die Erklärungen sind identisch mit denen vom Java-Quellcode.

package main

import "math"

func main () {
	var limit uint = 1000
	var zahl, zaehler uint
	var primzahl bool
	
	for zahl = 2; zahl <= limit; zahl++ {
		
		primzahl = true
		
		for zaehler = 2; zaehler <= zahl/2; zaehler++ {
			if math.Mod(float64(zahl), float64(zaehler)) == 0 {
				primzahl = false
				break
			}
		}
		
		if primzahl == true {
			println(zahl, " ist eine Primzahl")
		}
	}
	
	
}

Primzahlen

Literatur

• The New Book of Prime Number Records, Paolo Ribenboim, Springer Verlag 1996, ISBN 0-387-94457-5
• My Numbers, my Friends, Paolo Ribenboim, Springer Verlag, ISBN 0-387-98911-0
• Prime Numbers - A Computational Perspective, Richard Crandall & Carl Pomerance, Springer Verlag, ISBN 0-387-25282-7

Internet

• Wikipedia:
  • w:Primzahl
  • w:Primzahlsatz
  • w:Primzahllücke
  • w:Sophie-Germain-Primzahl
  • w:Cunningham-Kette
  • w:kleiner fermatscher Satz
  • w:Lucas-Folge

• andere Quellen
  • Final Answers Modular Arithmetic
  • Ergänzungen und Irrtümer zu dem Buch "The new Book of Prime Number Records" von Paolo Ribenboim
  • Primzahlbeweise