~2025-47925-7 am 29. August 2025 um 03:52 Uhr

2025-08-29T03:52:37Z

Neue Seite

Als '''Primzahlgenerator''' bezeichnet man in der [[Informatik]] einen [[Algorithmus]] <math>f(n)</math>, so dass für [[natürliche Zahl]]en <math>n</math> der Wert <math>f(n)</math> die <math>n</math>-te [[Primzahl]] ist. In der [[Mathematik]] und speziell der [[Zahlentheorie]] entspricht das Formeln, die besonders viele Primzahlen liefern '''(Formeln für Primzahlen).''' Bisher wurde noch kein [[Effizienz (Informatik)|effizienter]] Primzahlgenerator gefunden, insbesondere existiert keine praktikable geschlossene Formel zur Generierung von Primzahlen.

Es gibt allerdings Formeln, bei denen eine gewisse Wahrscheinlichkeit besteht, dass eine erzeugte Zahl eine Primzahl ist, so dass die erzeugten Zahlen noch darauf getestet werden müssen, ob sie prim sind. Im Artikel werden auch andere Formeln behandelt, die nicht praxistauglich sind, die aber in der mathematischen Literatur bezüglich der Frage diskutiert wurden, ob sie viele Primzahlen liefern.

== Geschichte ==

Einer der ältesten Algorithmen zur Bestimmung von Primzahlen ist das [[Sieb des Eratosthenes]], bei dem nacheinander aus einer Liste der natürlichen Zahlen diejenigen Zahlen gestrichen werden, die Vielfache der jeweils kleinsten noch nicht gestrichenen Zahl sind. Dadurch bleiben die Primzahlen innerhalb der Ausgangsliste übrig.

Schon [[Leonhard Euler|Euler]] gab die Formeln <math>n^2+n+17</math> und <math>n^2-n+41</math> an, die für <math>0 \leq n < 16</math> bzw. <math>0 \leq n < 41</math> Primzahlen liefern. Auch für größere Werte von <math>n</math> liefern die beiden Formeln viele [[Primzahl]]en, weil das Ergebnis nie durch Primzahlen <math>p < 17</math> bzw. <math>p < 41</math> ganzzahlig teilbar ist. Allgemein gibt es viele solche Formeln <math>an^2+bn+c</math>, wodurch sich die auffällige [[Ulam-Spirale]] erklärt. Man kann [[Quadratisches Polynom|quadratische]] [[Irreduzibles Polynom|irreduzible Polynome]] mittels eines Siebalgorithmus als Primzahlgenerator verwenden.<ref>{{Internetquelle |autor=Helmes, Bernhard |url=https://www.devalco.de/poly_sec.php |titel=Prime generators on quadratic irreducible polynomials |sprache=Englisch |abruf=2016-10-06}}</ref> Jedes [[Polynom]] liefert die Hälfte der Primzahlen. Dafür werden folgende quadratischen Polynome: verwendet: <math>4n^2+1</math> (Primzahlen [[Kongruenz (Zahlentheorie)|kongruent]] 1 [[modulo]] 4), <math>2n^2+1</math> (Primzahlen kongruent 1 oder 3 modulo 8) und <math>2n^2-1</math> (Primzahlen 1 oder 7 modulo 8) Mittels dieser quadratischen Polynome werden alle Primzahlen als [[Teilbarkeit|Teiler]] der Polynome generiert.<ref>{{Internetquelle |autor=Helmes, Bernhard |url=https://www.devalco.de/#106 |titel=Primzahlgenerierende quadratische irreducible Polynome |datum=2020 |sprache=englisch |abruf=2025-05-05}}</ref><ref>{{Internetquelle |autor=Helmes. Bernhard |url=https://www.devalco.de/quadr_Sieb_2x%5E2+1.php#5 |titel=Prime sieving for the polynomial f(n)=2n2+1 |abruf=2025-05-05}}</ref> Es gibt aber nach [[Adrien-Marie Legendre]] kein Polynom, das für alle oder [[fast alle]] Werte der Variablen in den [[Natürliche Zahl|natürlichen Zahlen]] Primzahlen ergibt. Die Frage, welche ganzzahligen Polynome unendlich viele Primzahlen erzeugen, ist Gegenstand der [[Bunjakowski-Vermutung]].

Die beliebteste ist die der [[Mersenne-Primzahl|Mersenne-Zahl]] <math>M_n = 2^n-1</math>, bei der <math>M_n</math> eine Primzahl ist. Durch die besonderen Eigenschaften der Teiler von Mersenne-Zahlen eignen sie sich für die Suche nach möglichst großen Primzahlen.

[[Pierre de Fermat|Fermat]] vermutete, dass alle Zahlen der Form <math>2^{2^n}+1</math> prim sind; man nennt sie [[Fermat-Zahl]]en. Tatsächlich ist aber für <math>n>4</math> keine derartige Primzahl bekannt.

Auch bekannt ist eine Anwendung des Satzes von [[Euklid]], bei der zum [[Primorial]] <math>p\#</math> (Produkt aller Primzahlen von 2 bis <math>p</math>) eine 1 addiert wird:

: <math>p\# + 1 = 2 \cdot 3 \cdot 5 \dotsm p + 1</math>

<math>p\# + 1</math> ist prim für <math>p = 2, 3, 5, 7, 11, 31, 379, 1019, 1021, \dotsc</math> ({{OEIS|A005234}}) Es ist unbekannt, ob es unendlich viele Primzahlen gibt, die so erzeugt werden.

=== Primzahlerzeugende quadratische Polynome ===

Ein ''primzahlerzeugendes Polynom'' ist ein [[quadratisches Polynom]] mit der Gleichung <math>f(x)=ax^2+bx+c</math> mit <math>a \ge 1</math> und <math>c \ge 1</math> und der Eigenschaft, dass es ein <math>d>2</math> gibt, für das <math>f(0), f(1), ..., f(d-1)</math> Primzahlen sind. Das größtmögliche solche <math>d</math> nennt man die ''primzahlerzeugende Länge'' von <math>f(x)</math>.

Für Polynome mit der Gleichung <math>f(x)=x^2+x+q</math> ist <math>q=41</math> die von [[Leonhard Euler|Euler]] entdeckte größte Primzahl mit der Eigenschaft, dass <math>f(0),f(1), ..., f(q-1)</math> Primzahlen sind.

[[Adrien-Marie Legendre|Legendre]] stellte fest, dass Polynome mit der Gleichung <math>f(x)=2x^2+q</math> für <math>q=3,5,11,29</math> die größtmögliche primzahlerzeugende Länge <math>q</math> besitzen.

1914 fand A. Lévy heraus, dass <math>f(x)=3x^2+3x+23</math> eine primzahlerzeugende Länge von 22 hat.

[[Balthasar van der Pol]] und Speziali entdeckten 1951, dass <math>f(x)=6x^2+6x+31</math> die primzahlerzeugende Länge von 29 hat.<ref>[[Paulo Ribenboim]]: Die Welt der Primzahlen 2. Aufl., Springer-Lehrbuch, Springer-Verlag Berlin Heidelberg 2011, ISBN 978-3-642-18078-1, S. 151–152.</ref>

=== Weitere Formeln ===

* <math>n! - 1</math> ist prim für <math>n = 3, 4, 6, 7, 12, 14, 30, 32, 33, 38, 94, 166, \dotsc</math> ({{OEIS|A002982}})
* <math>n! + 1</math> ist prim für <math>n = 1, 2, 3, 11, 27, 37, 41, 73, 77, 116, 154, \dotsc</math> ({{OEIS|A002981}})
* Primzahlen der Form <math>\operatorname{kgV}(1,\dotsc,n)+1</math> sind: <math>2, 3, 7, 13, 61, 421, 2521, 232792561, \dotsc</math> ({{OEIS|A049536}})

Nach dem [[Dirichletscher Primzahlsatz|Dirichletschen Primzahlsatz]] enthält eine arithmetische Folge <math>a \cdot m + b</math> (wobei <math>a</math>, <math>b</math> [[Teilerfremdheit|teilerfremd]] sind und <math>m</math> die natürlichen Zahlen durchläuft) unendlich viele Primzahlen (aber auch zusammengesetzte Zahlen). Allerdings gibt es nach [[Ben Green]] und [[Terence Tao]] für jedes <math>k</math> arithmetische Folgen (festgelegt durch <math>a, b</math>), die Primzahlen für <math>k</math> aufeinanderfolgende Werte liefern.<ref>{{MathWorld|Green-TaoTheorem|Green-Tao Theorem}}</ref> Zum Beispiel liefert:

: <math>43142746595714191+5283234035979900 \cdot k</math>

Primzahlen für <math>k=0, \dotsc, 25</math>. Die Methode entspricht dem Fall linearer Polynome.

== Trivialer Generator ==

Ein trivialer Primzahlgenerator kann folgendermaßen [[Induktion (Mathematik)|induktiv]] definiert werden:

# <math>f(1)=2</math>
# <math>f(2)=3</math>
# für <math>n \geq 2</math> ist <math>f(n+1)</math> die auf <math>f(n)</math> folgende Primzahl, wobei einfach alle Zahlen ab <math>f(n)+2</math> aufsteigend darauf [[Probedivision|getestet]] werden, ob sie eine Primzahl sind.

Dieses Verfahren ist aber recht ineffektiv, da nacheinander alle ungeraden natürlichen Zahlen getestet werden müssen. Als Alternative bietet es sich an, mittels einer [[Sieb (Zahlentheorie)|Siebmethode]], z. B. [[Sieb des Eratosthenes]] oder [[Sieb von Atkin]], eine genügend lange Liste von Primzahlen zu erstellen und diese dann bis zur gewünschten Primzahl zu durchlaufen. Dabei bestimmt man manchmal zunächst primzahlähnliche Mengen ([[Fastprimzahl]]en).

== Satz von Wilson ==

Eine nicht sehr praktikable Formel für alle Primzahlen beruht auf dem [[Satz von Wilson]]. Die Formel lautet unter Verwendung der [[Abrundungsfunktion]]:

: <math>f(n) = \left\lfloor \frac{n! \bmod (n+1)}{n} \right\rfloor (n-1) + 2</math> für natürliche Zahlen <math>n</math>

Nach dem Satz von Wilson ist <math>n+1</math> prim genau dann, wenn <math>n! \bmod (n+1) = n</math>. Daraus folgt, dass die Formel nur Primzahlen liefert und jede Primzahl außer 2 genau einmal. Denn ist <math>n+1</math> prim, so ist <math>\left\lfloor \frac{n! \bmod (n+1)}{n} \right\rfloor =1</math> und <math>f(n)=n+1</math>. Ist <math>n+1</math> nicht prim, so ist <math>\left\lfloor \frac{n! \bmod (n+1)}{n} \right\rfloor =0</math> und <math> f(n)=2</math>.

== Diophantische Mengen für Primzahlen ==

Nach den Arbeiten zu [[Diophantische Gleichung#Hilberts zehntes Problem|Hilberts zehntem Problem]] gibt es ein System von endlich vielen diophantischen Gleichungen (Polynomen über den [[Ganze Zahl|ganzen Zahlen]]), die als Lösung alle Primzahlen und nur diese haben. Nach [[Juri Wladimirowitsch Matijassewitsch]] sollte es so ein System mit neun oder weniger Variablen geben. James P. Jones und Kollegen gaben 1976 ein System von 14 Polynomen in 26 Variablen an.<ref>James P. Jones, Daihachiro Sato, Hideo Wada, Douglas Wiens: ''Diophantine representation of the set of prime numbers.'' American Mathematical Monthly, Band 83, 1976, S. 449–464.</ref> Explizit besteht das System aus den Gleichungen:

: <math>\alpha_0 = wz + h + j - q = 0</math>

: <math>\alpha_1 = (gk + 2g + k + 1)(h + j) + h - z = 0</math>

: <math>\alpha_2 = 16(k + 1)^3(k + 2)(n + 1)^2 + 1 - f^2 = 0</math>

: <math>\alpha_3 = 2n + p + q + z - e = 0</math>

: <math>\alpha_4 = e^3(e + 2)(a + 1)^2 + 1 - o^2 = 0</math>

: <math>\alpha_5 = (a^2 - 1)y^2 + 1 - x^2 = 0</math>

: <math>\alpha_6 = 16r^2y^4(a^2 - 1) + 1 - u^2 = 0</math>

: <math>\alpha_7 = n + \ell + v - y = 0</math>

: <math>\alpha_8 = (a^2 - 1)\ell^2 + 1 - m^2 = 0</math>

: <math>\alpha_9 = ai + k + 1 - \ell - i = 0</math>

: <math>\alpha_{10} = ((a + u^2(u^2 - a))^2 - 1)(n + 4dy)^2 + 1 - (x + cu)^2 = 0</math>

: <math>\alpha_{11} = p + \ell(a - n - 1) + b(2an + 2a - n^2 - 2n - 2) - m= 0 </math>

: <math>\alpha_{12} = q + y(a - p - 1) + s(2ap + 2a - p^2 - 2p - 2) - x = 0</math>

: <math>\alpha_{13} = z + p\ell(a - p) + t(2ap - p^2 - 1) - pm = 0</math>

mit den Variablen <math>a, \dotsc, z</math>. Dann und nur dann, wenn eine Lösung in natürlichen Zahlen existiert, ist die Variable <math>k+2</math> eine Primzahl.

Das lässt sich auch in eine Ungleichung zusammenfassen:

: <math>(k+2)(1-\alpha_0^2-\alpha_1^2-\cdots-\alpha_{13}^2) > 0</math>

Wenn man für die einzelnen Variablen natürliche Zahlen einsetzt, ist <math>k+2</math> genau dann eine Primzahl, wenn die Ungleichung erfüllt ist.

Es gibt auch ein die Primzahlen (und nur diese) erzeugendes System von <math>n</math> diophantischen Gleichungen mit nur zehn Variablen, allerdings mit sehr hohem Grad (in der Größenordnung <math>10^{45}</math>). Nach Thoralf Skolem kann man auch immer ein solches System mit nur Polynomen höchstens vierten Grades finden, allerdings ist in diesem Fall die Zahl der Variablen sehr hoch (mindestens 58, soweit bekannt).<ref>James P. Jones: ''Universal diophantine equation.'' [[Journal of Symbolic Logic]], Band 47, 1982, S. 549–571.</ref> Die Methoden sind bisher von keinem praktischen Nutzen.

== Formel von Mills ==

W. H. Mills zeigte 1947,<ref>Mills: ''A prime-representing function.'' Bulletin of the AMS, Band 53, 1947, S. 604.</ref> dass es eine reelle Zahl <math>A</math> gibt, sodass

: <math>\left \lfloor d_n \right \rfloor = \left \lfloor A^{3^{n}} \right \rfloor</math>

für alle natürlichen Zahlen <math>n</math> prim ist. Man kann unter Annahme der [[Riemannsche Vermutung|Riemannschen Vermutung]] zeigen, dass das kleinste solche <math>A</math> (die sogenannte [[Mills’ Konstante|Mill’sche Konstante]]) einen Wert von etwa <math>1{,}3063778838630806904686144926 \dots</math> hat.<ref>{{OEIS|A051021}}.</ref> Die mit der Formel erzeugten Primzahlen heißen Mills-Primzahlen: <math>\left \lfloor d_1 \right \rfloor = 2</math>, <math>\left \lfloor d_2 \right \rfloor = 11</math>, <math>\left \lfloor d_3 \right \rfloor = 1361.</math> Da über <math>A</math> wenig bekannt ist (noch nicht einmal, ob die Konstante rational oder irrational ist), hat die Formel aber keinen praktischen Wert.

== Formel von Wright ==

Eine ähnliche Formel wie die von Mills fand [[E. M. Wright]].<ref>E. M. Wright: ''A prime-representing function.'' American Mathematical Monthly, Band 58, 1951, S. 616–618.</ref> Wright zeigte, dass es eine reelle Zahl <math>\alpha</math> gibt, sodass

: <math>\left \lfloor g_n \right \rfloor = \left \lfloor 2^{\dots^{2^{2^\alpha}}} \right \rfloor</math>

prim ist für alle <math>n \ge 1</math>.

Dabei ist <math>g_n</math> rekursiv definiert:

: <math>g_0 = \alpha</math>
: <math>g_{n+1} = 2^{g_n}</math> für <math>n \ge 0</math>

Wright gab mit <math>\alpha = 1{,}9287800 \dots</math> auch die ersten Dezimalstellen von <math>\alpha</math> an. Das ergibt die Primzahlen <math>\left \lfloor g_1 \right \rfloor = \left \lfloor 2^{\alpha} \right \rfloor = 3</math>, <math>\left \lfloor g_2 \right \rfloor = 13</math> und <math>\left \lfloor g_3 \right \rfloor = 16381</math>.
Es zeigt sich, dass mit einem Wert von <math>\alpha \approx 1{,}9287800</math>
:<math>\left \lfloor g_4 \right \rfloor = \left \lfloor 2^{2^{2^{2^{\alpha}}}}\right \rfloor = 19139664204631104...822015417386540 </math>

(die Punkte bedeuten 4900 nicht dargestellte Dezimalstellen) eine Zahl mit 4932 Dezimalstellen ist, die aber ''gerade'' (das heißt, keine Primzahl) ist, das heißt, dieser Wert von <math>\alpha</math> muss leicht korrigiert werden.<ref>Robert Baillie: Wright's Fourth Prime [https://arxiv.org/pdf/1705.09741.pdf]</ref>
Für die folgenden Primzahlen braucht man noch weit mehr Dezimalstellen.

Da die Formel auf der Kenntnis von <math>\alpha</math> beruht, ist sie praktisch ebenso nutzlos wie die von Mills.

== Conways Primzahlgenerator ==

Für die primzahlerzeugende ''Maschine'' (PRIMEGAME) von [[John Horton Conway]]<ref>[[Richard K. Guy]]: ''Conway's Prime Producing Machine.'' Mathematics Magazine, Band 56, 1983, S. 26–33.</ref> siehe [[FRACTRAN]]. Die Methode ist allerdings ebenfalls nicht praktikabel zur Generierung von Primzahllisten.

== Primzahlgenerator für endliche Primzahlmengen ==

[[Ross Honsberger]]<ref>Honsberger: ''More Mathematical Morsels.'' Mathematical Association of America 1991, S. 108 (Morsel 20).</ref> gibt einen einfachen Beweis für folgenden Satz:

Man teile die ersten <math>n</math> Primzahlen beliebig auf zwei [[disjunkt]]e Mengen <math>A, B</math> auf, sodass <math>A \cup B = \{2, \dotsc, p_n \}</math>. Sei <math>a</math> das Produkt der Elemente von <math>A</math> und <math>b</math> das der Elemente von <math>B</math>. <math>A</math> darf auch [[Leere Menge|leer]] sein, dann ist <math>a = 1</math> ([[leeres Produkt]]). Falls nun <math>a+b < p_{n+1}^2</math>, dann ist <math>a+b</math> eine Primzahl, und <math>|a-b|</math> ist prim, wenn <math>1 < |a-b| < p_{n+1}^2</math>.

Beispiel: <math>p_n=5</math> (betrachtet werden dann nur Zahlen kleiner als <math>p_{n+1}^2=7^2=49</math>):
: <math>2 \cdot 3 + 5 = 11, \quad 2 \cdot 3 - 5 = 1</math>
: <math>2 \cdot 5 + 3 = 13, \quad 2 \cdot 5 - 3 = 7</math>
: <math>3 \cdot 5 + 2 = 17, \quad 3 \cdot 5 - 2 = 13</math>
: <math>2 \cdot 3 \cdot 5 + 1 = 31, \quad 2 \cdot 3 \cdot 5 - 1 = 29</math>

Zweites Beispiel: <math>p_n=11</math> (betrachtet werden dann nur Zahlen kleiner als <math>p_{n+1}^2=13^2=169</math>):
: <math>2 \cdot 11 + 3 \cdot 5 \cdot 7 = 127</math>
: <math>3 \cdot 5 \cdot 11 - 2 \cdot 7 = 151</math>
Jedoch sind
: <math>3 \cdot 5 + 2 \cdot 7 \cdot 11 = 169,</math>
: <math>2 \cdot 3 \cdot 5 \cdot 11 - 7 = 323</math>
''nicht'' kleiner als 169 und daher nicht prim.

== Primzahlgenerator mit JavaScript ==

<syntaxhighlight lang="html">
<!DOCTYPE html>
<html>
<body>
<h1>Primzahlgenerator</h1>
<div id="ausdruck"></div>

<script>
anzahl = 0;
primzahlen = '';

for(var vllt_prim = 1; vllt_prim <= 1000; vllt_prim++)
{
prim = true;

for(var nat_zahl = 1; nat_zahl <= 1000; nat_zahl++)
{
for(var teiler = 2; teiler <= 1000; teiler++)
{
if(vllt_prim/teiler == nat_zahl && vllt_prim/teiler != 1)
{
prim = false;
}
}
}

if(prim == true)
{
primzahlen += vllt_prim + ', ';
anzahl++;
}
}

primzahlen = primzahlen.substr(0, primzahlen.length - 2);
ergebnis = anzahl + ' Primzahlen (von 1 bis 1000):<br><br>' + primzahlen;
ausdruck = document.getElementById('ausdruck');
ausdruck.innerHTML = ergebnis;
</script>

</body>
</html>
</syntaxhighlight>

== Weblinks ==

* {{MathWorld|PrimeFormulas|Prime Formulas}}

== Einzelnachweise ==
<references />

[[Kategorie:Primzahl]]
[[Kategorie:Zahlentheoretischer Algorithmus]]
[[Kategorie:Ungelöstes Problem der Informatik]]

Primzahlgenerator - Versionsgeschichte

~2025-47925-7 am 29. August 2025 um 03:52 Uhr